题解：AT_abc380_e [ABC380E] 1D Bucket Tool

并查集基础练习题，我们记录连通块的左/右端点 l,r，父亲节点对应的颜色 col，颜色的个数 siz，那么每一次合并只用考虑区间左/右侧一个格子是否和现在的格子颜色相同，维护 l,r 即可。合并时要注意使用的变量会不会因为更改导致前后表达的意思不同。

#include<bits/stdc++.h>

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();

#define ll long long
#define i128 __int128

using namespace std;
inline int read() {
    int xx= 0;int f= 1;
    char c = getchar();
    while(c<'0'||c>'9') { 
        if(c=='-') f= -1;
        c= getchar();
    }
    while(c>='0'&&c<='9') {
        xx= (xx<<1)+(xx<<3)+(c^48);
        c= getchar();
    }
    return xx*f;
}
#define maxn 500050
int fa[maxn];
int col[maxn];
int l[maxn],r[maxn],siz[maxn];
int n,q;
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]); }
signed main() {
    in2(n,q);
    For(i,1,n) col[i]=i,fa[i]=i,l[i]=i,r[i]=i,siz[i]=1;
    while(q--) {
        int opt=read();
        if(opt==1) {
            int x=read(),c=read();
            int X=find(x);
            if(col[X]==c) continue;
            siz[col[X]]-=r[X]-l[X]+1;
            col[X]=c;
            siz[col[X]]+=r[X]-l[X]+1;
            if(l[X]>1) {
                int L=find(l[X]-1);
                if(col[L]==c) {
                    l[X]=l[L];
                    fa[L]=X;
                }
            }
            if(r[X]<n) {
                int R=find(r[X]+1);
                if(col[R]==c) {
                    r[X]=r[R];
                    fa[R]=X;
                }
            }
        } else {
            int c=read();
            cout<<siz[c]<<'\n';
        }
    }
}