F - Max Matrix - 第二回日本最強プログラマー学生選手権

F - Max Matrix

• 長さ $N$ の数列 $a$ と、長さ $M$ の数列 $b$ がある
• 最初、$a,b$ の要素は全て $0$
• $Q$ 個のクエリを処理する。$i$ 個目のクエリでは $T_i,X_i,Y_i$ が与えられる
  • $T_i=1$ のとき、$a_{Xi}$ を $Y_i$ に置き換える
  • $T_i=2$ のとき、$b_{Xi}$ を $Y_i$ に置き換える
  • 毎回のクエリの処理直後に $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \max(a_i,b_j)$ の値を出力する
• $1 \le N,M \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le Y_i \le 10^8$

最初、全要素が0なので答えは言うまでも無く0。

たとえば $a$ の1個 $a_i$ を $5$ から $10$ に変えたときに、全体の答えがどうなるか考えると、

• $b$ の、$10$ より小さい値について
  • その個数分だけ、新規に $\max(a_i,b_j)=10$ になる組が増える
    • 答えが「$該当個数 \times 10$」増加する
• $b$ の、$5$ 以下の値について
  • その個数分だけ、今まで $\max(a_i,b_j)=5$ だった組が上に変わる
    • 答えが「$該当個数 \times 5$」減少する
• $b$ の、$5$ より大きく $10$ より小さい値について
  • その総和だけ、$\max(a_i,b_j)=b_j$ として今まで答えに寄与していた分が無くなる
    • 答えが「該当する $b_j$ の総和」分だけ減少する

これで全て。
なので、差分だけ更新していくことで、クエリに高速に答えられそう。

なお、$10$ から $5$ に変わるなど値が減少するときは、3つめの増加と減少が逆転する。

範囲の個数や総和を求めたいので、セグメント木やFenwick Treeで管理すればよい。
「$a$ 用、$b$ 用」「個数用、総和用」で合計4つ、必要になる。

$Y_i$ の取り得る範囲が $10^8$ と大きいので、座標圧縮の必要がある。
今回は「$a_i$ を $Y_{old}$ から $Y_{new}$ に変えるとき、この間の個数や総和」が求まればよい、つまり $Y_i$ の大小関係さえ保たれていれば範囲指定できるので、 $Y_i$ として出てくる値をソートして小さい順に $0,1,2,...$ に対応させれば、$Q$ の長さ $2 \times 10^5$ として扱うことができる。

範囲の境界（以下なのか未満なのか、など）に注意。
どちらでもよいが、$a_i=b_j$ となる $b_j$ があり、今まで $\max(a_i,b_j)=b_j$ だった場合、それを「$\max(a_i,b_j)=a_i$ に変わったと見なし、更新対象に含めるのか（同じ値が引かれ、足されるので実質は変化ない）」「変化無しとして更新対象に含めないのか」は、3種類の更新の中で統一しておく必要がある。

Python3