AT_abc380_e [ABC380E] 1D Bucket Tool

Link

不知道自己在干嘛，一直在考虑分块。如果有老哥会分块做法的话希望留言/kel。

我的做法是考虑重构树的类似结构。

一开始的时候我们看做有 n 个点，对每个点维护覆盖的左右端点，以及颜色。

对于修改操作，我们先把 x 所在的连通块的代表的点改成颜色 c，然后观察 x 左边的连通块以及右边的连通块是否相同，如果相同那就合并起来。

注意到只有当前块的颜色改变，所以我们只用维护一个数组 t_x 表示颜色 x 的数量，然后两次单点修改即可。

合并的话，就是新建立一个结点，连向需要合并的两个连通块，同时更新新节点的信息。

这样做是对的，是因为合并操作不会是可逆的，一旦某个连通块变成同一颜色，那么在后续操作里面这个块里面所有点的颜色一定是一起变化的。

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define int long long
#define DEBUG cout<<"when can get npy"<<endl;
int n,T,fa[N],t[N];
struct node{
    int l,r,col,siz;
}c[N];
int Find(int x){
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}
signed main(){
    cin>>n>>T;
    for(int i=1;i<=n;i++)   fa[i]=i,c[i].l=i,c[i].r=i,c[i].col=i,c[i].siz=1,t[i]=1;
    int tot=n;
    while(T--){
        int op;
        cin>>op;
        if(op==1){
            int x,C;
            cin>>x>>C;
            int now=Find(x);
            int pre=c[now].col;
            t[c[now].col]-=c[now].siz; 
            t[C]+=c[now].siz;
            c[now].col=C,pre=C;
            int l=c[now].l,r=c[now].r;
//          if(x==3&&C==2)  cout<<now<<endl;
            if(l-1>0&&c[Find(l-1)].col==pre){
                int prenow=Find(l-1);
                tot++;
                c[tot].l=c[prenow].l,c[tot].r=c[now].r,c[tot].col=pre,
                c[tot].siz=c[prenow].siz+c[now].siz;
                fa[now]=fa[prenow]=tot,fa[tot]=tot;
//              if(x==3&&C==2)  cout<<c[tot].siz<<endl;
            }
            if(r+1<=n&&c[Find(r+1)].col==pre){
                int prenow=Find(r+1),prelst=Find(now);
                tot++;
                c[tot].l=c[prelst].l,c[tot].r=c[prenow].r,
                c[tot].col=pre,c[tot].siz=c[prenow].siz+c[prelst].siz;
                fa[prelst]=fa[prenow]=tot,fa[tot]=tot;
            }
        }
        else{
            int x;
            cin>>x;
            cout<<t[x]<<endl;
        }
    }
    return 0;
}