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

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_f

前提知識

• BIT
• 座標圧縮

解説

https://atcoder.jp/contests/jsc2021/submissions/21832371

クエリ問題に対する取り組み方というのはそれほど多くない。
今回の問題は差分計算をする問題である。

差分計算

q番目のクエリを処理した答えがansであるときに、q+1番目のクエリの答えを計算する。
差分計算方法の1つは、「変更前の計算を引く」→「変更後の計算を追加する」である。
クエリ1とクエリ2はどちらも修正方法は全く変わりないので、片方だけ紹介する。

クエリ1

a[X[i]]をY[i]に書き換える。
[i]を書くのが面倒なので、x,yと書くことにする。
まず、もともとのa[x]に入っている値がansにどのような影響を与えているかを考える。
配列bとのmaxを掛け合わせて総和を取っている部分が対象となるが、

• a[x]以下
• a[x]より大きい

の2つの場合に分けて考えることができる。

a[x]以下

配列の値がa[x]以下であれば、max(b,a[x])=a[x]となる。
なので、ansにa[x] * (配列bの中でa[x]以下の個数)が入っていることになる。
これをansから引こう。
この個数を計算するにはBITを使うのがよい。
Bcnt[x] := 数xの個数
としておいて、区間総和をBITで取る。

a[x]より大きい

配列の値がa[x]より大きいなら、max(b,a[x])=bとなる。
なので、ansには(配列bの中でa[x]より大きい数)の総和が入っていることになる。
これもansから引こう。
Btot[x] := 数xの総和（＝数xの個数×x）
としておいて、これも区間総和をBITで取ればいい。

この2つの場合について、変更前のansからこれらの場合の数を引いて、a[x]=yと更新をして、再度同様の計算をしてその数を足してやれば
新しいansを計算することができる。

実装

ここまでの思考の流れが分かっていれば十分である。
最後の問題は実装である。
Bcnt[x]のように数を添え字に入れるが、Yの上限を見ると10⁸であるので普通に作るとメモリが足りない。
よって、クエリをすべて先読みして、座標圧縮をすることでここは解決できる。
平衡二分木を使えば殴れるが、どっちもどっちな感じがする。

int N, M, Q, T[201010], X[201010], Y[201010];
int A[201010], B[201010];
BIT<ll> Acnt(201010), Bcnt(201010);
BIT<ll> Atot(201010), Btot(201010);
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;
    rep(i, 0, Q) cin >> T[i] >> X[i] >> Y[i];

    auto ZY = compress1(Y, Q + 1);
    Acnt.add(0, N);
    Bcnt.add(0, M);

    ll ans = 0;
    rep(q, 0, Q) {
        if (T[q] == 1) {
            int x = X[q] - 1;
            int y = Y[q];
            ans -= Bcnt.get(0, A[x] + 1) * ZY[A[x]];
            ans -= Btot.get(A[x] + 1, 201010);

            Acnt.add(A[x], -1);
            Atot.add(A[x], -ZY[A[x]]);

            A[x] = y;

            ans += Bcnt.get(0, A[x] + 1) * ZY[A[x]];
            ans += Btot.get(A[x] + 1, 201010);

            Acnt.add(A[x], 1);
            Atot.add(A[x], ZY[A[x]]);
        }
        else {

            int x = X[q] - 1;
            int y = Y[q];
            ans -= Acnt.get(0, B[x] + 1) * ZY[B[x]];
            ans -= Atot.get(B[x] + 1, 201010);

            Bcnt.add(B[x], -1);
            Btot.add(B[x], -ZY[B[x]]);

            B[x] = y;

            ans += Acnt.get(0, B[x] + 1) * ZY[B[x]];
            ans += Atot.get(B[x] + 1, 201010);

            Bcnt.add(B[x], 1);
            Btot.add(B[x], ZY[B[x]]);
        }
        printf("%lld\n", ans);
    }
}