時刻 $t$ で行 $R$ を黒く塗るとする。操作前の行 $R$ における黒マスの個数は $\# \left\{ c \mid \mathrm{col\_time}_c < \mathrm{row\_time}_R \right\}$ である。また、操作後は $\mathrm{row\_time}_R = t$ となるので、行 $R$ における黒マスの個数は $\# \left\{ c \mid \mathrm{col\_time}_c < t \right\}$ である。

したがって、クエリ1の処理による黒マスの個数の差分は

\# \left\{ c \mid \mathrm{col\_time}_c < t \right\} - \# \left\{ c \mid \mathrm{col\_time}_c < \mathrm{row\_time}_R \right\}

と計算できる。

クエリ2

時刻 $t$ で列 $C$ を白く塗るとする。操作前の列 $C$ における黒マスの個数は $\# \left\{ r \mid \mathrm{row\_time}_C < \mathrm{col\_time}_r \right\}$ である。また、操作後は $\mathrm{col\_time}_C = t$ となるので、列 $C$ における黒マスの個数は $0$ である。したがって、クエリ2の処理による黒マスの個数の差分は

- \# \left\{ r \mid \mathrm{row\_time}_C < \mathrm{col\_time}_r \right\}

と計算できる。

データ構造の決定と実装

ここまでの話をまとめると、結局やりたいことは $\mathrm{row\_time}$ や $\mathrm{col\_time}$ について、

ある値 $x$ よりも小さい / 大きい値を持つ要素数の取得
クエリごとの値の1点更新

を高速に行うということになる。

そこで、 Fenwick Tree を用いて、 $\mathrm{row\_time}$ と $\mathrm{col\_time}$ の値の分布を管理することにする。具体的には、

row[t]： $\mathrm{row\_time}_r = t$ となる $r$ の個数
col[t]： $\mathrm{col\_time}_c = t$ となる $c$ の個数

とする。これは、ACLのfenwick_treeを用いると、これらの処理をそれぞれ $O(\log Q)$ の計算量で行うことができる。

例えば、col.sum(0, x)なら $\mathrm{col\_time}_c < x$ となる列数を取得できるし、N - row.sum(0, x+1)なら $\mathrm{row\_time}_r > x$ となる行数を取得できる。

また、以下の処理で行 $R$ の時刻を $t$ に更新することができる。

1.row.add(row_time[R], -1);
2.row_time[R] = t;
3.row.add(row_time[R], 1);

以上より、全体として $O(Q \log Q)$ の計算量で解くことができた。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using ll = long long;
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N, Q;
18.    cin >> N >> Q;
19. 
20.    fenwick_tree<ll> row(Q + 1), col(Q + 1);
21.    vector<int> row_time(N + 1, 0), col_time(N + 1, 0);
22. 
23.    row.add(0, N);
24.    col.add(0, N);
25. 
26.    ll ans = 0;
27.    int time = 0;
28.    while (Q--)
29.    {
30.        int t;
31.        cin >> t;
32.        time++;
33. 
34.        if (t == 1) {
35.            int R;
36.            cin >> R;
37. 
38.            ans += col.sum(0, time) - col.sum(0, row_time[R]);
39.            row.add(row_time[R], -1);
40.            row_time[R] = time;
41.            row.add(row_time[R], 1);
42.        }
43.        else {
44.            int C;
45.            cin >> C;
46. 
47.            ans -= (N - row.sum(0, col_time[C] + 1));
48.            col.add(col_time[C], -1);
49.            col_time[C] = time;
50.            col.add(col_time[C], 1);
51.        }
52. 
53.        cout << ans << endl;
54.    }
55. 
56.    return 0;
57.}