計算量が \(H\) や \(W\) に依存しない解法です．ベースとなる考え方は ordered set を使わない解法 と一緒です．リンク先の解説ではあらかじめ \(H,W\) 個の UnionFind を作っていますが，必要な場所だけ UnionFind で管理する方針を取ります．破壊したマスと整数を map を使うなどして 1 対 1 対応させながら，破壊区間のマージを同様の方法で行えばよいです．破壊されるマスは高々 \(4Q\) 個なので，サイズが \(4Q\) の UnionFind を用意しておけば十分です．計算量は map がボトルネックとなり \(O(Q \log Q)\) です．

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.L = [-1] * n
        self.R = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.L[x] = min(self.L[x], self.L[y])
        self.R[x] = max(self.R[x], self.R[y])
        self.parents[y] = x

    def get_LR(self, x):
        x = self.find(x)
        return (self.L[x], self.R[x])


H, W, Q = map(int, input().split())
uf_row = UnionFind(4 * Q)
uf_col = UnionFind(4 * Q)

idx = 0
d = {}


def erase(x, y):
    global idx
    if 1 <= x <= H and 1 <= y <= W:
        d[(x, y)] = idx
        uf_row.L[idx] = y
        uf_row.R[idx] = y
        uf_col.L[idx] = x
        uf_col.R[idx] = x
        if (x, y - 1) in d:
            uf_row.merge(idx, d[(x, y - 1)])
        if (x, y + 1) in d:
            uf_row.merge(idx, d[(x, y + 1)])
        if (x - 1, y) in d:
            uf_col.merge(idx, d[(x - 1, y)])
        if (x + 1, y) in d:
            uf_col.merge(idx, d[(x + 1, y)])
        idx += 1


for _ in range(Q):
    x, y = map(int, input().split())
    if (x, y) not in d:
        erase(x, y)
        continue
    i = d[(x, y)]
    Lx, Rx = uf_col.get_LR(i)
    Ly, Ry = uf_row.get_LR(i)
    erase(Lx - 1, y)
    erase(Rx + 1, y)
    erase(x, Ly - 1)
    erase(x, Ry + 1)

print(H * W - idx)

”`