题目解法：并查集 + 分块优化 + 邻接关系维护

问题分析

本题模拟画图软件的填充功能，核心是连通块染色问题：

• 初始时，相同颜色的相邻像素构成连通块

• 染色操作会改变某个连通块的颜色，并可能导致与相邻连通块合并

• 需要高效处理 $Q \leq 10^5$ 次操作，网格大小 $R,S \leq 2000$（总像素 $n \leq 4\times 10^6$）

算法思路

核心思想

• 并查集管理连通块：将相同颜色的相邻像素合并到同一个集合

• 分块优化：按连通块大小分为大块和小块，采用不同的维护策略

• 邻接关系缓存：记录每个连通块的相邻连通块信息

• 颜色变更传播：更新颜色时，检查是否与相邻连通块合并

复杂度分析

时间复杂度

• 初始化：$O(n \log n)$，其中 $n = R \times S$

每次操作：

• 小连通块：$O(\text{邻居数量})$，最坏 $O(n)$

• 大连通块：$O(\log n)$（并查集查找）+ $O(\text{邻接更新})$

• 总体：$O(n \log n + Q \sqrt{n} \log n)$

空间复杂度：$O(n)$

• 并查集数组：$O(n)$

• 邻接关系：$O(n)$

• 分块信息：$O(\sqrt{n} \times n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, M = 1e5 + 5, K = 255;
int n, m, q, B, c[N], fa[N], id[N], siz[N], cnt, p[N];
basic_string<int> v[N];
unordered_map<int, vector<int>> w[K];
bitset<K> s[N];

// 并查集查找（带路径压缩）
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

// 构建大连通块的邻接信息
void build(int x) {
    id[x] = ++cnt;
    for (auto y : v[x]) {
        y = find(y);
        w[cnt][c[y]].push_back(y);  // 按颜色分组邻居
        s[x][id[y]] = 1;  // 标记邻接关系
        s[y][cnt] = 1;
    }
}

// 合并两个连通块
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    
    // 按大小合并，保证树平衡
    if (siz[x] < siz[y]) swap(x, y);
    fa[y] = x;
    
    if (siz[x] > B) {
        // 大连通块合并：更新预计算的邻接信息
        for (auto z : v[y]) {
            z = find(z);
            if ((z ^ x) && (z ^ y)) {
                w[id[x]][c[z]].push_back(z);
                v[x].push_back(z);
                s[x][id[z]] = 1;
                s[z][id[x]] = 1;
            }
        }
    } else {
        // 小连通块合并：直接更新邻接列表
        for (auto z : v[y]) {
            z = find(z);
            if ((z ^ x) && (z ^ y)) {
                v[x].push_back(z);
                s[x][id[z]] = 1;
            }
        }
        // 如果合并后变为大连通块，构建邻接信息
        if (siz[x] + siz[y] > B) build(x);
    }
    siz[x] += siz[y];
}

int main() {
    scanf("%d%d", &n, &m);
    
    // 读取初始颜色
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", c + (i - 1) * m + j);
    
    // 初始化并查集
    for (int i = 1; i <= n * m; i++)
        fa[i] = i, siz[i] = 1;
    
    B = 2 * sqrt(n * m);  // 分块阈值
    
    // 构建初始邻接关系（上下左右四个方向）
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x = (i - 1) * m + j;
            if (i > 1) v[x].push_back(x - m);
            if (j > 1) v[x].push_back(x - 1);
            if (i < n) v[x].push_back(x + m);
            if (j < m) v[x].push_back(x + 1);
        }
    
    // 合并初始连通块
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x = (i - 1) * m + j;
            if (i > 1 && c[x] == c[x - m]) merge(x, x - m);
            if (j > 1 && c[x] == c[x - 1]) merge(x, x - 1);
            if (i < n && c[x] == c[x + m]) merge(x, x + m);
            if (j < m && c[x] == c[x + 1]) merge(x, x + 1);
        }
    
    scanf("%d", &q);
    
    // 处理染色操作
    while (q--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        x = find((x - 1) * m + y);  // 找到目标连通块
        y = z;  // 新颜色
        
        if (c[x] == y) continue;  // 颜色相同，跳过
        
        c[x] = y;  // 更新颜色
        
        // 更新邻接信息中的颜色映射
        for (int i = 1; i <= cnt; i++)
            if (s[x][i]) w[i][c[x]].push_back(x);
        
        if (siz[x] <= B) {
            // 小连通块：遍历所有邻居
            int cnt_nei = 0;
            for (auto y : v[x])
                if (find(y) != x) p[++cnt_nei] = y;
            
            v[x].clear();
            for (int i = 1; i <= cnt_nei; i++)
                v[x].push_back(p[i]);
            
            // 检查是否与邻居合并
            for (int i = 1; i <= cnt_nei; i++)
                if (c[x] == c[find(p[i])]) merge(x, p[i]);
        } else {
            // 大连通块：使用预计算的邻居信息
            int cnt_nei = 0;
            for (auto y : w[id[x]][c[x]])
                if (find(y) != x && c[find(y)] == c[x])
                    p[++cnt_nei] = y;
            
            w[id[x]][c[x]].clear();
            for (int i = 1; i <= cnt_nei; i++)
                merge(x, p[i]);
        }
    }
    
    // 输出最终结果
    for (int i = 1; i <= n; i++, putchar('\n'))
        for (int j = 1; j <= m; j++)
            printf("%d ", c[find((i - 1) * m + j)]);
    
    return 0;
}