It suffices to track how many black cells are added (removed) by each query. Let us consider how many black cells are added by a type-1 query.

When row \(R\) is touched for the first time, all cells in row \(R\) are white, so the number of black cells increases by \(N\).

When it is not the first time, the cells in row \(R\) have been painted black last time it was touched, and now we have to bring back the white cells painted by type-\(2\) queries into black.

Thus, the number of newly black cells equals how many columns have been touched by type-\(2\) queries since the last time row \(R\) was touched (or how many distinct type-\(2\) queries have been applied).

This is a special case of AWC0015E. We may start explaining that problem, but here we will instead explain a solution to our special case using a Fenwick Tree / Binary Indexed Tree (a data structure that supports updating an element and finding a segment sum fast). (The general case can be solved too by sorting the queries.)

Manage a length-\(Q\) sequence \(f\) in a Fenwick Tree while processing the queries in order. Let \(f_i\) be \(1\) if the \(i\)-th query is an already-executed type-2 query that is the last query (at that point) that touches the column, and \(0\) otherwise. (In short, we count only the last one query for each row to remove duplicates.) Then, if the \(i\)-th query is a type-1 query, the increase of black cells can be computed as \(\sum_{j = \text{last}_R}^{i - 1} f_j\), if the \(\text{last}_R\)-th query is the last query that touched row \(R\). By managing \(\text{last}_R\) in an ordinary array, the total time complexity is \(O(Q \log Q + N)\).

The decrease of black cells by a type-2 query can be computed in the same way; this time, when column \(C\) is touched for the first time, count the rows touched by type-1 queries so far.

Sample code in Python (+ Python port of AtCoder Library

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)