欸？根号？——根号算法学习笔记

· · 算法·理论

0. 写在前面

打模拟赛时发现有根号算法的题，但只想到了一半，仔细一想又觉得自己一点不会，所以想着作一个小小的总结，毕竟这一块完全是知识盲区。

由于是用来梳理知识的，所以概念不会特别详细还请见谅。然后因为我水平太菜，所以不会有太难的题目，兑。想学习具体算法的建议找题目自行练习，本文侧重于讲解思想上的一些东西。

但说实话这东西考简单题的概率极低，至少我在正赛没碰到过，都是相对有难度的，所以这篇文章看看只图一乐就好，毕竟还是要自己多做一点相关的题目啊……

1. 根号算法定义

根号算法，又称分块算法、平方根算法，是一类基于分治思想的算法统称。顾名思义，根号算法的时间复杂度中含有 \sqrt{n}。这个根号从哪里来？在这些算法中，通常采用分治的思想，将问题分解为与 \sqrt{n} 相关的子问题，从而降低时间复杂度。通常来说，根号算法相对好写，且时间复杂度也不算太高，算是比较实用的算法。

2. 根号算法用途

对于一些和区间等有关的操作，在数据量特别大时，如果没有单次操作 \log{n} 的思路，可以尝试使用根号算法去作为一种替代的方案，因而根号算法会被戏称为 poor man's logarithm。

但是对于一些 \log{n} 级别算法难以解决，或者是正常写会爆时间但很难做到进一步优化时，根号算法就会有奇效：它能用包含 \sqrt{n} 的时间复杂度处理许多 \log{n} 级别算法难以实现的操作，也能用分治压缩时间。那这时候根号算法可谓是“另辟蹊径”，用看似暴力的方式去解决许多复杂的问题。

3. 根号算法基本思路

最核心的思想就是：将程序要处理的东西进行划分。这个东西可能是要求维护的数组，也可能是单次操作的规模，还有可能是题目给出的询问。总之，根号算法就是通过划分这一操作进行处理的。这些不同的划分方式会带来不同的应用，而这正是接下来我们要讨论的东西。

4. 根号算法实际应用

4.1 分块

大家最耳熟能详喜闻乐见（并非）的根号算法就是分块了。分块的 \sqrt{n} 复杂度源自于其将要维护的数据划分成若干块，不妨记作 s 块。对于普通的分块题，每次修改与查询操作的最坏复杂度均为 O(\frac{n}{s}+s)，因为显然一整块是可以进行统一处理的。根据基本不等式，当 s 取到 \sqrt{n} 时，单次操作时间复杂度为 O(\sqrt{n})，总时间复杂度为 O(n\sqrt{n})，吊打朴素 O(n^2) 的暴力。

下面用两道题目，从不同的角度去看待分块。

4.1.1 P3374 【模板】树状数组 1

什么？不是有 O(n\log{n}) 的方法吗？为什么还用分块？

选用这道题是为了体现分块这一算法的普适性，就是说带 \log 的解法能做它大部分情况下也能做，只是时间复杂度大了一点而已，理解起来和写起来相对都比较容易。

对于这道题的分块，显然我们统计块内所有数的和，单点修改 O(1) 实现，然后查询时暴力查找不完整的块，完整的块直接调用即可，单次操作复杂度为 O(\sqrt{n})。没错由于实在是太基础了所以并没有什么进阶的题目。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 5e5+5;
int n, m, a[Max], l[Max], r[Max], belong[Max];
int block, num, sum[Max];
void build()//分块
{
    block = sqrt(n);
    num = n/block;
    if(n%block)num++;
    rep(i, 1, num)//块的左右端点
    {
        l[i] = (i-1)*block+1;
        r[i] = i*block;
    }
    r[num] = n;
    rep(i, 1, n)//每个点属于哪个块
        belong[i] = (i-1)/block+1;
    rep(i, 1, num)//块内数字和
        rep(j, l[i], r[i])sum[i] += a[j];
}
void add(int x, int val)//单点修改
{
    a[x] += val;
    sum[belong[x]] += val;
}
int query(int x, int y)//区间查询
{
    if(belong[x] == belong[y])
    {
        int res = 0;
        rep(i, x, y)res += a[i];
        return res;
    }
    int ans = 0;
    rep(i, x, r[belong[x]])ans += a[i];//暴力查找
    rep(i, l[belong[y]], y)ans += a[i];//同上
    rep(i, belong[x]+1, belong[y]-1)ans += sum[i];//直接调用预处理好的数据
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n)cin >> a[i];
    build();
    while(m--)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1)add(x, y);
        else cout << query(x, y) << "\n";
    }
    return 0;
}

:::

4.1.2 P4168 [Violet] 蒲公英

对于这道题目，我们似乎很难想到一个可行的 n\log{n} 级别算法（其实有特殊性质的可以做到该复杂度，这里不加以赘述）。但是如果我们用分块去维护块内众数，实现起来却非常简单：我们考虑每次计算 \sqrt{n} 级别数量的数来找到其中的最大值，显然我们将所有整块中的众数和非整块中的数全部拎出来比较出现次数即可，时间复杂度还是 O(n\sqrt{n})。

这里顺带提一嘴，分块的优势就是对于所有的整块可以显著的减小计算量，使得非整块进行暴力计算时仍然可以有相当优秀的时间复杂度。当然太大还是会被卡的，本人模拟赛就信仰写下分块然后超时了。

:::info[代码] 没有注释且码风较丑，建议看一下题解。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define int long long
const int Max = 4e4+5, N = 5e2+5;
int n, m, x, tot;
int a[Max], b[Max], s[Max];
int sum[N][Max];
int f[N][N];
int block, num, L[N], R[N], belong[Max];
inline int read()
{
    int f = 1, x = 0;
    char c = getchar();
    while(!isdigit(c))
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c))
    {
        x = 10*x + c - '0';
        c = getchar();
    }
    return f*x;
}
signed main()
{
    n = read();m = read();
    rep(i, 1, n)b[i] = a[i] = read();

    // 离散化
    sort(b+1, b+n+1);
    tot = unique(b+1, b+n+1)-b-1;
    rep(i, 1, n)a[i] = lower_bound(b+1, b+tot+1, a[i])-b;

    block = sqrt(n);
    num = (n-1)/block+1;
    rep(i, 1, num)
    {
        L[i] = block*(i-1)+1;
        R[i] = min(block*i, n);
    }
    rep(i, 1, n)belong[i] = (i-1)/block+1;

    rep(i, 1, num)
    {
        rep(j, L[i], R[i])sum[i][a[j]]++;
        rep(j, 1, tot)sum[i][j] += sum[i-1][j];
    }
    rep(i, 1, num)
    {
        rep(j, i, num)
        {
            int maxn = f[i][j-1];
            rep(k, L[j], R[j])
            {
                if(sum[j][a[k]]-sum[i-1][a[k]] > sum[j][maxn]-sum[i-1][maxn]||
                (sum[j][a[k]]-sum[i-1][a[k]] == sum[j][maxn]-sum[i-1][maxn]&&a[k] < maxn))
                    maxn = a[k];
            }
            f[i][j] = maxn;
        }
    }
    while(m--)
    {
        int l = (read()+x-1)%n+1;
        int r = (read()+x-1)%n+1;
        if(l > r) swap(l, r);
        int maxn = 0;
        int bl = belong[l], br = belong[r];
        if(br-bl <= 1)
        {
            rep(i, l, r)s[a[i]]++;
            rep(i, l, r)
            {
                if(s[a[i]] > s[maxn]||(s[a[i]] == s[maxn]&&a[i]<maxn))
                    maxn = a[i];
            }
            rep(i, l, r) s[a[i]] = 0;
        }
        else
        {
            rep(i, l, R[bl])s[a[i]]++;
            rep(i, L[br], r)s[a[i]]++;
            maxn = f[bl+1][br-1];
            rep(i, l, R[bl])
            {
                int cntmax = s[maxn]+sum[br-1][maxn]-sum[bl][maxn];
                int cntcur = s[a[i]]+sum[br-1][a[i]]-sum[bl][a[i]];
                if(cntcur > cntmax||(cntcur == cntmax&&a[i] < maxn))
                    maxn = a[i];
            }
            rep(i, L[br], r)
            {
                int cntmax = s[maxn]+sum[br-1][maxn]-sum[bl][maxn];
                int cntcur = s[a[i]]+sum[br-1][a[i]]-sum[bl][a[i]];
                if(cntcur > cntmax||(cntcur == cntmax&&a[i] < maxn))
                    maxn = a[i];
            }
            rep(i, l, R[bl]) s[a[i]] = 0;
            rep(i, L[br], r) s[a[i]] = 0;
        }
        x = b[maxn];
        printf("%lld\n", x);
    }
    return 0;
}

:::

4.2 莫队

好吧莫队算是现学现用了。

莫队算法的主要思路是：对于序列上的区间询问问题，离线排序，按一定顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案。那么这个 \sqrt{n} 从何而来呢？我们将这些询问进行排序，使得两个询问之间可以最大化的利用已计算的数据。排序后，左右端点一次查询移动的次数在一个固定范围内。详细证明详见 OI-Wiki（其实就是我懒得写了）。

我们这里只讨论基础的莫队板子，主要是理解其将询问分组排序对复杂度的显著优化。

4.2.1 P1494 [国家集训队] 小 Z 的袜子

莫队板子题。计算发现需要所有每种袜子的个数的平方之和，这显然可以 O(1) 修改。不懂的自己去学，这里不详细讲。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 5e4+5;
int block;
int n, m, c[Max];
struct node{
    int l, r, id;
    bool operator <(const node &x) const
    {
        if(l/block != x.l/block)return l/block < x.l/block;
        if((l/block)&1)return r < x.r;
        return r > x.r;
    }
};
struct frac{
    int p, q, id;
    static int gcd(int x, int y){return (!y?x:gcd(y, x%y));}
    frac(int pp = 0, int qq = 1, int dd = 0)
    {
        int d = gcd(pp, qq);
        p = pp/d, q = qq/d, id = dd;
    }
};
node ask[Max];
frac ans[Max];
bool cmp_ask(node x, node y){return x < y;}
bool cmp_ans(frac x, frac y){return x.id < y.id;}
int sum[Max], tot = 0;
void add(int x)
{
    tot -= sum[c[x]]*sum[c[x]];
    sum[c[x]]++;
    tot += sum[c[x]]*sum[c[x]];
}
void del(int x)
{
    tot -= sum[c[x]]*sum[c[x]];
    sum[c[x]]--;
    tot += sum[c[x]]*sum[c[x]];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n)cin >> c[i];
    block = sqrt(n);
    rep(i, 1, m)cin >> ask[i].l >> ask[i].r, ask[i].id = i;
    sort(ask+1, ask+m+1, cmp_ask);
    int l = 1, r = 0;
    rep(i, 1, m)
    {
        while(r < ask[i].r)add(++r);
        while(r > ask[i].r)del(r--);
        while(l < ask[i].l)del(l++);
        while(l > ask[i].l)add(--l);
        int res = ask[i].r-ask[i].l+1;
        if(ask[i].l == ask[i].r)ans[i] = frac(0, 1, ask[i].id);
        else ans[i] = frac(tot-res, res*(res-1), ask[i].id);
    }
    sort(ans+1, ans+m+1, cmp_ans); 
    rep(i, 1, m)cout << ans[i].p << "/" << ans[i].q << "\n";
    return 0;
}

:::

4.2.2 P4462 [CQOI2018] 异或序列

看到区间异或先前缀处理一下。不妨记 S_i = a_1 \oplus a_2 \oplus \dots \oplus a_i，那么 a_l \oplus a_{l+1} \oplus \dots \oplus a_r 即为 S_{l-1} \oplus S_r。我们转而去思考每次添加或减少一个数时对答案产生的影响，若处理的数为 S_i，则我们只需要知道 S_i \oplus k 有多少个即可计算出它的贡献，开一个数组即可实现单次操作 O(1)。

有两个细节需要注意，一个是区间操作的 l 要减 1，因为前缀中需要考虑的值包括 S_{l-1}，还有一个是计算贡献和修改出现次数的先后顺序，如果反了会在 k = 0 时出错，读者不妨思考一下。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
typedef long long ll;
const int Max = 1e5+5, N = 1e3+5;
int n, m, k, block, a[Max];
ll ans[Max];
struct query{
    int l, r, id;
    bool operator <(const query &x)const
    {
        if(l/block != x.l/block)return l < x.l;
        if((l/block)&1)return r < x.r;
        else return r > x.r;
    }
}ask[Max];
int cnt[Max];
ll sum = 0;
void add(int x)
{
    sum += cnt[a[x]^k];
    cnt[a[x]]++;
}
void del(int x)
{
    cnt[a[x]]--;
    sum -= cnt[a[x]^k];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;block = sqrt(n);
    rep(i, 1, n)cin >> a[i], a[i] ^= a[i-1];
    rep(i, 1, m)cin >> ask[i].l >> ask[i].r, ask[i].id = i;
    sort(ask+1, ask+m+1);
    int l = 1, r = 0;
    rep(i, 1, m)
    {
        while(l < ask[i].l-1)del(l++);
        while(l > ask[i].l-1)add(--l);
        while(r < ask[i].r)add(++r);
        while(r > ask[i].r)del(r--);
        ans[ask[i].id] = sum;
    }
    rep(i, 1, m)cout << ans[i] << "\n";
    return 0;
}

:::

4.2.3 P3604 美好的每一天

编号重排这个限制非常宽松，我们重点考虑这个性质，思考如何转移到莫队相关的问题上。我们发现：判断重排后是否能构成一个回文串等价于判断所有出现字母个数中至多有一个奇数，即维护每个字母出现次数，这恰恰是莫队可以维护的内容。

考虑进一步优化，我们只想知道出现次数的奇偶性，考虑异或处理，于是这道题便转化为了前面这道题，我们让每一个字母与一个二进制位一一对应就行了，计算贡献时要考虑每一个字母出现次数为奇数的情况。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 6e4+5, N = (1<<26)+5;
int n, m, a[Max], cnt[N], ans[Max], block;
struct node{
    int l, r, id;
    bool operator <(const node &x) const
    {
        if(l/block != x.l/block)return l/block < x.l/block;
        if((l/block)&1)return r < x.r;
        else return r > x.r;
    }
}ask[Max];
string s;
int res = 0;
void add(int x)
{
    res += cnt[a[x]]++;
    rep(i, 0, 25)
        res += cnt[a[x]^(1<<i)];
}
void del(int x)
{
    res -= --cnt[a[x]];
    rep(i, 0, 25)
        res -= cnt[a[x]^(1<<i)];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;block = sqrt(n);
    cin >> s;
    rep(i, 1, n)
        a[i] = a[i-1]^(1<<(int)(s[i-1]-'a'));
    rep(i, 1, m)
        cin >> ask[i].l >> ask[i].r, ask[i].id = i;
    sort(ask+1, ask+m+1);
    int l = 1, r = 0;
    rep(i, 1, m)
    {
        while(l < ask[i].l-1)del(l++);
        while(l > ask[i].l-1)add(--l);
        while(r < ask[i].r)add(++r);
        while(r > ask[i].r)del(r--);
        ans[ask[i].id] = res;
    }
    rep(i, 1, m)
        cout << ans[i] << "\n";
    return 0;
}

:::

4.3 根号分治

这一算法的主要思想就是将操作的数据规模分治处理。对于小规模的操作（通常取一次性操作数量 \leq\sqrt{n}），直接暴力处理；而对于大规模操作（通常取一次性操作数量 >\sqrt{n}），则对其进行预处理或特殊处理，降低时间复杂度。

为什么不对小规模的也进行预处理或特殊处理呢？因为没有必要。而且如果你这样做的话，反而会提升你的时间复杂度，因为许多处理对于小规模操作来说是无用的，处理除了耗时之外没有任何用处。比如说用数据结构维护带单 \log，对于小规模操作来说就是复杂度在暴力的基础上乘上 \log{n}，就好比你在遍历完数组后加一次排序，做的是无用功。

但是对于大规模操作而言，预处理或特殊处理则能显著减少暴力枚举的数目，从而排除无效状态。根号分治便是将这两种方法融合到一起从而提高效率的。

当然，只是讲的话看起来有点抽象。下面一样用两个具体例子来解释一下上面的思想。

4.3.1 P12751 [POI 2017 R2] 集装箱 Shipping containers

先想暴力做法：每次操作暴力修改所有的点，最劣复杂度为 O(n^2)，显然不行。我们发现当 d_i 比较大时操作时间反而十分优秀，考虑根号分治。

记 B = \sqrt{n}，对于所有 d_i > B，我们直接暴力修改，单次操作复杂度最多为 O(\sqrt{n})。那 d_i \leq B 的部分我们怎么处理呢？根号分治带来了一个非常好的性质，就是 d_i \leq B 的所有 d_i 个数不超过 \sqrt{n}，我们只需要想出一种统计完之后对于每个 d_i 可以 O(n) 处理的方法即可。这是离线的，所以显然差分可以完美解决这一问题，于是我们有总复杂度为 O(n \sqrt{n}) 的做法。

这里复杂度原本是 O(nB + \frac{n ^2}{B}) 的，因为我们根据基本不等式，B 取到 \sqrt{n}，总复杂度就是 O(n \sqrt{n})。

根号分治还有一个比较玄学的点就是，提前计算最大的 B 并直接使用反而比根据 n 现算跑的更快（你跑不过我你信吗），也算作是小技巧吧。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 1e5+5;
//友情提示：本题卡空间
int n, k, b, d[Max+20000][151], num[Max]; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;b = 150;
    rep(i, 1, k)
    {
        int ai, li, di;
        cin >> ai >> li >> di;
        if(di > b)
        {
            rep(j, 0, li-1)
                num[ai+di*j]++;
        }
        else
        {
            d[ai][di]++;
            d[ai+di*li][di]--;
        }
    }
    rep(i, 1, b)
    {
        rep(j, i, n)d[j][i] += d[j-i][i];
        rep(j, 1, n)num[j] += d[j][i];
    }
    rep(i, 1, n)cout << num[i] << " ";
    return 0;
}

:::

4.3.2 P8427 [COI 2020] Paint

没错我就是为了这盘醋包的饺子。

看到这道题，你的第一反应肯定是并查集。对！但是我们怎么合并呢？

思考一下，我们发现无非两种方法：

  1. 对于一个连通块，我们暴力查找与这个连通块相邻的所有连通块，如果颜色相等就直接更新。

  2. 我们提前记录下这个连通块周围的所有颜色包含的连通块，如果修改就直接调用存好的对应颜色的连通块信息并进行合并，无需查找过程。

看起来第二种方法确实聪明一点（其实是因为我赛时就这么想的），但是我们用这种方法要用数据结构维护，这样就带有 \log{n} 的额外复杂度（这里我们记 n = R \times S），总复杂度来到了惊人的 O(n^2\log{n})。

那么我们不妨仿照前面一题，部分暴力部分预处理，和前面一题一样，我们对于小的操作直接暴力找连通块，对于大的操作预处理相邻颜色信息。我们还是记阈值为 B，那么我们此时的时间复杂度为 O(nB + \frac{n^2}{B}\log{n})。

你发现了吗？这里如果我们将 B 设为 1 时恰好是只用第二种方法的复杂度，而 B 为 n^2 时恰好是纯暴力（只用第一种方法的复杂度）。我们这里 B 取 \sqrt{n\log{n}} 最优，最大就是在 1000 左右，干脆直接让 B = 1000 就行，3s 显然可以跑过去，于是这题就做完了。

当然，这道题分析起来的确不难，但是想要实现还是难度较大的，你可以选择不看题解自己做来锻炼码力。代码有详细解析，不懂的可以看一下。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a;i <= b;i++)
const int Max = 2e5+5, B = 1e3;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int R, S, q;
inline int id(int i, int j){return (i-1)*S+j;}
int col[Max];

class DSU//disjoint set union 并查集 
{
    int f[Max];
    public:
        DSU(){rep(i, 1, Max-3)f[i] = i;}
        int find(int x){return (f[x] == x?x:f[x] = find(f[x]));}
        int join(int x, int y)
        {
            x = find(x);y = find(y);
            if(x != y)f[x] = y;
            return y;
        }
        bool root(int x){return f[x] == x;}
};
DSU d;
set<int> g[Max];//用于小块dfs合并

bool large[Max];//用于大块找相邻合并 
set<int> sl;
map<int, map<int, set<int> > > mpl; 

void add_large(int i, int c, int x)//向与第i个块相邻的颜色为c的块中加入x
{
    mpl[i][c].insert(x);
}
void erase_large(int i, int c, int x)//向与第i个块相邻的颜色为c的块中删去x
{
    auto it = mpl.find(i);
    if(it == mpl.end())return ;
    auto itc = it->second.find(c);
    if(itc == it->second.end())return ;
    itc->second.erase(x);
    if(itc->second.empty())it->second.erase(itc);
}
void new_large(int i)//新增一个大块 
{
    large[i] = 1;sl.insert(i);
    auto &add = mpl[i];
    add.clear();
    for(auto x:g[i])
        add[col[x]].insert(x); 
}
int merge(int i, int j)//将大块与另外一个块进行合并
{
    i = d.find(i), j = d.find(j);
    if(i == j)return j;
    if(g[i].size() > g[j].size())swap(i, j);
    //i合并到j，将所有i内信息转移到j 
    for(int x:g[i]) 
    {
        g[x].erase(i);
        if(large[x])erase_large(x, col[i], i);
    }
    sl.erase(i);
    mpl.erase(i);
    for(int x:g[i])
    {
        if(x != j)
        {
            g[j].insert(x);
            g[x].insert(j);
            if(large[x])add_large(x, col[j], j);
        }
    }
    if(large[j])
    {
        for(auto x:g[i])
            if(x != j)add_large(j, col[x], x);
    }
    else if(large[i]||g[j].size() >= B)new_large(j);
    d.join(i, j);
    g[i].clear();
    return j;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> R >> S;
    //并查集合并 
    rep(i, 1, R)rep(j, 1, S)
    {
        cin >> col[id(i, j)];
        if(i > 1&&col[id(i, j)] == col[id(i-1, j)])d.join(id(i-1, j), id(i, j));
        if(j > 1&&col[id(i, j)] == col[id(i, j-1)])d.join(id(i, j-1), id(i, j));
    }
    //确定块与块之间的连接关系 
    rep(i, 1, R)rep(j, 1, S)
    {
        int fx = d.find(id(i, j));
        if(i > 1)
        {
            int fy = d.find(id(i-1, j));
            if(fx != fy)
            {
                g[fx].insert(fy);
                g[fy].insert(fx);
            }
        }
        if(j > 1)
        {
            int fy = d.find(id(i, j-1));
            if(fx != fy)
            {
                g[fx].insert(fy);
                g[fy].insert(fx);
            }
        }
    }
    //建立大块 
    rep(i, 1, R*S)
        if(d.root(i)&&g[i].size() >= B)new_large(i);;
    cin >> q;
    while(q--)
    {
        int r, s, c;
        cin >> r >> s >> c;
        int i = d.find(id(r, s));
        if(col[i] == c)continue;
        for(auto j:sl)
        {
            if(j != i&&g[i].count(j))
            {
                erase_large(j, col[i], i);
                add_large(j, c, i);
            }
        }
        col[i] = c;
        vector<int> pre;//保存将要合并的块 
        if(large[i])//如果是大块，直接调用保存好的相邻颜色信息 
        {
            auto it = mpl[i].find(c);
            if(it != mpl[i].end())
            {
                for(auto j:it->second)
                    pre.push_back(j);
            }
        }
        else//如果是小块，暴力查找 
        {
            for(auto j:g[i])
                if(col[j] == c)pre.push_back(j);
        }
        for(int j:pre)i = merge(i, j); 
    }
    rep(i, 1, R)
    {
        rep(j, 1, S)
            cout << col[d.find(id(i, j))] << " ";
        cout << "\n";
    }
    return 0;
}

:::

5 总结 & 闲话

第一次写笔记，所以有讲的不好的地方还请包涵，也欢迎在评论区指出，看到了我会改的。有好的题目也请推荐一下，说不定我哪一天就把它加上（咕咕咕）。

还有就是这类方法不仅可以当正解，实在不行你也能骗部分分不是吗……