题解：AT_abc380_e [ABC380E] 1D Bucket Tool

注意到每次修改的是一个区间，即对整个 同色连通块 修改，于是我们关心的是那些与自己同色的点，不难发现我们可以用 并查集 维护。

考虑带权并查集，对于每个集合我们维护其颜色 col，块的左端点 l，块的右端点 r。对于一次修改，设 x 为修改哪个连通块，我们对于答案将原 col_x 的贡献减去，再加上 c 的贡献，同时维护更新 col,l,r 数组即可。

具体来说，分别判断 l_x-1 的集合的 col 和 r_x+1 的集合 col 是否与 c 相等，如果相等的话将两集合合并。

难度评价是绿。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int fa[N],col[N],sz[N],l[N],r[N];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=0;i<N;i++){
        fa[i]=i;sz[i]=1;col[i]=i;
        l[i]=r[i]=i;
    }
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x,c;
            cin>>x>>c;
            x=find(x);
            //cout<<x<<'\n';
            if(col[x]==c) continue;
            sz[col[x]]-=r[x]-l[x]+1;sz[c]+=r[x]-l[x]+1;
            int lf=find(l[x]-1),rt=find(r[x]+1);
            if(l[x]-1>=1&&col[lf]==c){
                fa[lf]=x;
                l[x]=l[lf];
                //cout<<find(l[x]-1)<<' '<<fa[find(l[x]-1)]<<'\n';
            }
            if(r[x]+1<=n&&col[rt]==c){
                fa[rt]=x;
                r[x]=r[rt];
            }
            col[x]=c;
            //cout<<l[x]<<' '<<r[x]<<' '<<fa[l[x]]<<'\n';
        }else{
            int c;
            cin>>c;
            cout<<sz[c]<<'\n';
        }
    }
    return 0;
}