Number of Components (Codeforces 1303F)
Tags: Implement, dsu

You are given a matrix $$$n \times m$$$, initially filled with zeroes. We define $$$a_{i, j}$$$ as the element in the $$$i$$$-th row and the $$$j$$$-th column of the matrix.Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$ such that $$$s_1$$$ is the first cell, $$$s_k$$$ is the second cell, and for every $$$i \in [1, k - 1]$$$, $$$s_i$$$ and $$$s_{i + 1}$$$ are connected.You are given $$$q$$$ queries of the form $$$x_i$$$ $$$y_i$$$ $$$c_i$$$ ($$$i \in [1, q]$$$). For every such query, you have to do the following:  replace the element $$$a_{x, y}$$$ with $$$c$$$;  count the number of connected components in the matrix. There is one additional constraint: for every $$$i \in [1, q - 1]$$$, $$$c_i \le c_{i + 1}$$$.

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 300$$$, $$$1 \le q \le 2 \cdot 10^6$$$) — the number of rows, the number of columns and the number of queries, respectively.Then $$$q$$$ lines follow, each representing a query. The $$$i$$$-th line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$c_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le c_i \le \max(1000, \lceil \frac{2 \cdot 10^6}{nm} \rceil)$$$). For every $$$i \in [1, q - 1]$$$, $$$c_i \le c_{i + 1}$$$.

Output: Print $$$q$$$ integers, the $$$i$$$-th of them should be equal to the number of components in the matrix after the first $$$i$$$ queries are performed.


Sample Inputs:
3 2 10
2 1 1
1 2 1
2 2 1
1 1 2
3 1 2
1 2 2
2 2 2
2 1 2
3 2 4
2 1 5

Sample Outputs:
2
4
3
3
4
4
4
2
2
4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (m + 1) + v

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, m, q) = map(int, input().split())
l = (n + 1) * (m + 1)
p = max(1000, 2 * pow(10, 6) // (n * m))
z0 = [0] * q
(la, nx0) = ([-1] * l, [-1] * q)
cnt = [0] * (p + 1)
for i in range(q):
    (x, y, c) = map(int, input().split())
    cnt[c] += 1
    z = f(x, y)
    z0[i] = z
    if la[z] ^ -1:
        nx0[la[z]] = i
    la[z] = i
(c1, c2) = ([0] * q, [0] * (q + 1))
root = [i for i in range(l)]
rank = [1 for _ in range(l)]
visit = [0] * l
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
c = 0
for i in range(1, p + 1):
    if not cnt[i]:
        continue
    c0 = c
    c += cnt[i]
    v = 0
    (a, b) = ([], [])
    for j in range(c0, c):
        z = z0[j]
        (x, y) = divmod(z, m + 1)
        if c <= nx0[j]:
            a.append(nx0[j])
        elif nx0[j] == -1:
            b.append(z)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
        c1[j] = v
    for j in range(c0, c):
        z = z0[j]
        (root[z], rank[z], visit[z]) = (z, 1, 0)
    v = 0
    for z in b:
        (x, y) = divmod(z, m + 1)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
    c2[q] += v
    for j in sorted(a, reverse=True):
        z = z0[j]
        (x, y) = divmod(z, m + 1)
        v0 = 0
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v0 += 1
        c2[j - 1] += v0
        v += v0
    c2[c - 1] -= v
    for j in range(c0, c):
        z = z0[j]
        (root[z], rank[z], visit[z]) = (z, 1, 0)
(v, a) = (0, [])
b = [0] * l
for i in range(q):
    z = z0[i]
    (x, y) = divmod(z, m + 1)
    if not b[z]:
        a.append(i)
        b[z] = 1
for x in range(1, n + 1):
    for y in range(1, m + 1):
        z = f(x, y)
        if b[z]:
            continue
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
c2[q] += v
for i in a[::-1]:
    z = z0[i]
    (x, y) = divmod(z, m + 1)
    v0 = 0
    visit[z] = 1
    for (dx, dy) in d:
        (nx, ny) = (x + dx, y + dy)
        if not 0 < nx <= n or not 0 < ny <= m:
            continue
        nz = f(nx, ny)
        if not same(z, nz) and visit[nz]:
            unite(z, nz)
            v0 += 1
    if i:
        c2[i - 1] += v0
for i in range(q - 1, -1, -1):
    c2[i] += c2[i + 1]
ans = ['?'] * q
for i in range(q):
    ans[i] = str(n * m - c1[i] - c2[i])
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (m + 1) + v

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, m, q) = map(int, input().split())
l = (n + 1) * (m + 1)
p = max(1000, 2 * pow(10, 6) // (n * m))
z0 = [0] * q
(la, nx0) = ([-1] * l, [-1] * q)
cnt = [0] * (p + 1)
for i in range(q):
    (x, y, c) = map(int, input().split())
    cnt[c] += 1
    z = f(x, y)
    z0[i] = z
    if la[z] ^ -1:
        nx0[la[z]] = i
    la[z] = i
(c1, c2) = ([0] * q, [0] * (q + 1))
root = [i for i in range(l)]
rank = [1 for _ in range(l)]
visit = [0] * l
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
c = 0
for i in range(1, p + 1):
    if not cnt[i]:
        continue
    c0 = c
    c += cnt[i]
    v = 0
    (a, b) = ([], [])
    for j in range(c0, c):
        z = z0[j]
        (x, y) = divmod(z, m + 1)
        if c <= nx0[j]:
            a.append(nx0[j])
        elif nx0[j] == -1:
            b.append(z)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
        c1[j] = v
    for j in range(c0, c):
        z = z0[j]
        (root[z], rank[z], visit[z]) = (z, 1, 0)
    v = 0
    for z in b:
        (x, y) = divmod(z, m + 1)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
    c2[q] += v
    for j in sorted(a, reverse=True):
        z = z0[j]
        (x, y) = divmod(z, m + 1)
        v0 = 0
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v0 += 1
        c2[j - 1] += v0
        v += v0
    c2[c - 1] -= v
    for j in range(c0, c):
        z = z0[j]
        (root[z], rank[z], visit[z]) = (z, 1, 0)
(v, a) = (0, [])
b = [0] * l
for i in range(q):
    z = z0[i]
    (x, y) = divmod(z, m + 1)
    if not b[z]:
        a.append(i)
        b[z] = 1
for x in range(1, n + 1):
    for y in range(1, m + 1):
        z = f(x, y)
        if b[z]:
            continue
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
c2[q] += v
for i in a[::-1]:
    z = z0[i]
    (x, y) = divmod(z, m + 1)
    v0 = 0
    visit[z] = 1
    for (dx, dy) in d:
        (nx, ny) = (x + dx, y + dy)
        if not 0 < nx <= n or not 0 < ny <= m:
            continue
        nz = f(nx, ny)
        if not same(z, nz) and visit[nz]:
            unite(z, nz)
            v0 += 1
    if i:
        c2[i - 1] += v0
for i in range(q - 1, -1, -1):
    c2[i] += c2[i + 1]
ans = ['?'] * q
for i in range(q):
    ans[i] = str(n * m - c1[i] - c2[i])
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (m + 1) + v

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, m, q) = map(int, input().split())
l = (n + 1) * (m + 1)
p = max(1000, 2 * pow(10, 6) // (n * m))
(x0, y0) = ([0] * q, [0] * q)
(la, nx0) = ([-1] * l, [-1] * q)
cnt = [0] * (p + 1)
for i in range(q):
    (x, y, c) = map(int, input().split())
    (x0[i], y0[i]) = (x, y)
    cnt[c] += 1
    z = f(x, y)
    if la[z] ^ -1:
        nx0[la[z]] = i
    la[z] = i
(c1, c2) = ([0] * q, [0] * (q + 1))
root = [i for i in range(l)]
rank = [1 for _ in range(l)]
visit = [0] * l
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
c = 0
for i in range(1, p + 1):
    if not cnt[i]:
        continue
    c0 = c
    c += cnt[i]
    v = 0
    (a, b) = ([], [])
    for j in range(c0, c):
        (x, y) = (x0[j], y0[j])
        z = f(x, y)
        if c <= nx0[j]:
            a.append(nx0[j])
        elif nx0[j] == -1:
            b.append(z)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
        c1[j] = v
    for j in range(c0, c):
        z = f(x0[j], y0[j])
        (root[z], rank[z], visit[z]) = (z, 1, 0)
    v = 0
    for z in b:
        (x, y) = divmod(z, m + 1)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
    c2[q] += v
    for j in sorted(a, reverse=True):
        (x, y, v0) = (x0[j], y0[j], 0)
        z = f(x, y)
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v0 += 1
        c2[j - 1] += v0
        v += v0
    c2[c - 1] -= v
    for j in range(c0, c):
        z = f(x0[j], y0[j])
        (root[z], rank[z], visit[z]) = (z, 1, 0)
(v, a) = (0, [])
b = [0] * l
for i in range(q):
    (x, y) = (x0[i], y0[i])
    z = f(x, y)
    if not b[z]:
        a.append(i)
        b[z] = 1
for x in range(1, n + 1):
    for y in range(1, m + 1):
        z = f(x, y)
        if b[z]:
            continue
        visit[z] = 1
        for (dx, dy) in d:
            (nx, ny) = (x + dx, y + dy)
            if not 0 < nx <= n or not 0 < ny <= m:
                continue
            nz = f(nx, ny)
            if not same(z, nz) and visit[nz]:
                unite(z, nz)
                v += 1
c2[q] += v
for i in a[::-1]:
    (x, y, v0) = (x0[i], y0[i], 0)
    z = f(x, y)
    visit[z] = 1
    for (dx, dy) in d:
        (nx, ny) = (x + dx, y + dy)
        if not 0 < nx <= n or not 0 < ny <= m:
            continue
        nz = f(nx, ny)
        if not same(z, nz) and visit[nz]:
            unite(z, nz)
            v0 += 1
    if i:
        c2[i - 1] += v0
for i in range(q - 1, -1, -1):
    c2[i] += c2[i + 1]
ans = [n * m - i - j for (i, j) in zip(c1, c2)]
sys.stdout.write('\n'.join(map(str, ans)))