题目传送门

Solution

可以用并查集来维护。对于每一个块，维护其颜色以及左右端点。重新涂色的时候，判断涂完色后的块的颜色是否与相邻块的颜色相同，是则用并查集合并一下。

同时维护每种颜色格的数量，查询时直接输出就行了。

Code

#include<bits/stdc++.h>
using namespace std;
#define mxn 500010
int n,q,f[mxn],sze[mxn],col[mxn],l[mxn],r[mxn];
int fnd(int x){
    return x==f[x]?x:f[x]=fnd(f[x]);
}
void merge(int x,int c){
    int fx=fnd(x);
    int L=l[fx],R=r[fx];
    if(col[fx]==c)return;
    sze[col[fx]]-=R-L+1,col[fx]=c,sze[c]+=R-L+1;
    if(L>1){
        int fl=fnd(L-1);
        if(col[fl]==col[fx])f[fl]=fx,l[fx]=l[fl];
    }
    if(R<n){
        int fr=fnd(R+1);
        if(col[fr]==col[fx])f[fr]=fx,r[fx]=r[fr];
    }
}
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)f[i]=col[i]=l[i]=r[i]=i,sze[i]=1;
    while(q--){
        int opt,x,c;cin>>opt;
        if(opt==1)cin>>x>>c,merge(x,c);
        else cin>>c,cout<<sze[c]<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1;while(T--)solve();
    return 0;
}