题解：AT_abc380_e [ABC380E] 1D Bucket Tool

我不会告诉你我在结束后 8 分钟做出来了

这个题可以将一些颜色相同的相邻单元格抽象成一个集合（也就是后面的一个块），而改变颜色就是改变这个块的颜色标签。于是想到并查集，我们来一步一步将问题逐个击破。

这里规定一下，一个块的老大指的是并查集的每一个集合中 p_i=i 的节点（也就是 find 函数找的）。

在引入一个数组 col。col_i 表示一个单元格的颜色（不过由于并查集的优良特性，只有一个块的老大的 col 是正确的）。

问题一：如果一个块改变颜色后与相邻的块颜色相同，怎么办？

考虑并查集的合并。如果改变颜色后与相邻的块颜色相同，那就将这两个块合并为一个新的块。于是写出这样的代码：

if(x>1&&col[find(x-1)]==c) join(x-1,x);
if(x<n&&col[find(x+1)]==c) join(x,x+1);

但如果这么写是会出问题的（我就被这里卡了）。如果我们修改一个长度为三的块的中间为相邻块的颜色，那理论上这两个块应该合并。但由于 x-1 属于这个块，所以就会出现问题。具体看这张图：

为了防止出现这个错误，我们可以引入一个 mn 数组和 mx 数组，分别表示一个块的最小节点编号和最大节点编号。而相邻两个块就应该是 mn_x-1 和 mx_x+1。这两个数组可以在合并时更新。

问题2（难点）：如何统计答案？

我们需要引入两个数组：sum 数组和 s 数组。sum_i 表示 i 节点的孩子数量；s_i 表示第 i 种颜色的节点数量。

我们考虑当一个块变色时，这个块原来的颜色应该会减少这个块的点的数量，而新的颜色应该会增加这个块的节点数量。也就是代码中的

s[col[find(x)]]-=sum[find(x)];
s[c]+=sum[find(x)];

好了，终于可以放代码了：

#include<iostream>
using namespace std;
#define int long long //可有可无
const int N=5e5+10;
int p[N],col[N],sum[N],s[N],mn[N],mx[N];
int find(int x){ //非常标准的并查集
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}
void join(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) sum[x]+=sum[y],p[y]=x; //一定要判定 x!=y
    mx[x]=max(mx[x],mx[y]); //更新最小节点编号
    mn[x]=min(mn[x],mn[y]); //更新最大节点编号
}
bool query(int x,int y){
    return find(x)==find(y);
}
signed main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) //像屎的初始化
        p[i]=i,col[i]=i,sum[i]=1,s[i]=1,mn[i]=i,mx[i]=i;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x,c;
            cin>>x>>c;
            s[col[find(x)]]-=sum[find(x)]; //统计答案
            s[c]+=sum[find(x)];
            col[find(x)]=c; //变色
            //合并
            if(x>1&&col[find(mn[find(x)]-1)]==c) join(mn[find(x)]-1,x);
            if(x<n&&col[find(mx[find(x)]+1)]==c) join(x,mx[find(x)]+1);
        }
        else{
            int c; //这要还看不懂就可以退役了
            cin>>c;
            cout<<s[c]<<endl;
        }
    }
    return 0; //拜拜程序
}

最后说个注意事项：

1. 程序第 12 行一定要加判定，不然会多算！！！
2. 萌新的拙作，大佬勿喷。
3. 求过，求点赞，求评论。