各クエリで黒マスが何個増える（減る）か分かれば十分です。以下、タイプ 1 のクエリで黒マスが何個増えるか考えます。

行 \(R\) が初めて操作対象になったとき、行 \(R\) のマスはすべて白であり、黒マスが \(N\) 個増えます。

行 \(R\) が操作対象になったのが初めてでないとき、行 \(R\) のマスは行 \(R\) が前回操作対象になったときに黒になっており、その後タイプ 2 のクエリで白く塗られたマスを黒に戻すことになります。

従って、行 \(R\) が前回操作対象になってからタイプ 2 のクエリの対象になった列が何個あるか（あるいは何種類のタイプ 2 のクエリが行われたか）求まれば、それが黒マスの増加数です。

これは AWC0015E の特殊な場合です。ここでそちらの解説に移っても構いませんが、ここでは Fenwick Tree / Binary Indexed Tree（数列の要素の変更と区間和の計算をともに高速に行うデータ構造）を使って今回の特殊な場合を解く方法を述べます。（一般の場合もクエリをソートすれば同様に解けます。）

長さ \(Q\) の数列 \(f\) を Fenwick Tree で管理しながらクエリを順に処理します。\(f_i\) の値は、\(i\) 回目のクエリが実行済みのタイプ 2 のクエリであってその列に対する（その時点で）最後のクエリであるなら \(1\)、そうでないなら \(0\) とします（要するに、各列について最後の \(1\) 回のクエリのみ数えることで同じ列の重複を省きます）。すると、\(i\) 回目のクエリがタイプ 1 であるとき、そこでの黒マスの増加数は、行 \(R\) が前回操作対象になったクエリが \(\text{last}_R\) 回目であるとして \(\sum_{j = \text{last}_R}^{i - 1} f_j\) と計算できます。\(\text{last}_R\) を通常の配列で管理すると、全体の時間計算量は \(O(Q \log Q + N)\) です。

タイプ 2 のクエリで黒マスが何個減るかも同様に求められますが、列 \(C\) が初めて操作対象になったときはそれまでにタイプ 1 のクエリの対象になった行を数えます。

Python（+ AtCoder Library の Python ポート）での実装例

from atcoder.fenwicktree import FenwickTree

N, Q = map(int, input().split())
f = [FenwickTree(Q + 1) for _ in range(2)]
b = 0
last = [[-1] * (N + 1), [0] * (N + 1)]

for i in range(1, Q + 1):
    t, x = map(int, input().split())
    t -= 1
    if last[t][x] == -1:
        b += N
    else:
        kind = f[1 - t].sum(last[t][x], i)
        b += kind if t == 0 else -kind
        f[t].add(last[t][x], -1)
    f[t].add(i, 1)
    last[t][x] = i
    print(b)