At_abc380_e 1D Bucket Tool 题解

__yun__ · 2024-11-17 09:40:09 · 题解

思路：

用并查集合并同色块，用链表维护每个同色块的前一个和后一个同色块，再维护一下每个同色块的大小以及每种颜色的数量即可。

可以用并查集的树根代表每个同色块，这样每次修改只需修改树根即可。

若该同色块修改后与其前驱或后继同色，则把他们合并。具体的，在并查集中合并把两个块合并，随后把不作为树根的那个块从链表中删除。

Code:

#include<bits/stdc++.h>
//#define int long long
#define rd read<int>()
#define rdl read<ll>()
#define pb emplace_back
#define mkp make_pair
#define fr first
#define se second
#define Endl putchar('\n')
#define Space putchar(' ')
using namespace std;
using pii=pair<int,int>;
typedef long long ll;
const int mod=998244353,inf=0x3f3f3f3f;
const ll Inf=0x3f3f3f3f3f3f3f3f;
template<class T> inline T read(){
    T s=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){s=(s<<3)+(s<<1)+c-'0';c=getchar();}
    return s*f;
}
template<typename T> inline void write(T x){
    static int st[40],Top;
    if(x<0){putchar('-');x=-x;}
    if(!x)putchar('0');
    while(x){st[++Top]=x%10;x/=10;}
    while(Top){putchar(st[Top--]^'0');}
}
inline char readc(){
    char c=getchar();
    while(c=='\n'||c=='\r'||c==' '||c==EOF)c=getchar();
    return c;
}
const int N=5e5+10;
int n,q,f[N],sz[N],col[N],a[N],pre[N],nxt[N]; 
int find(int x){
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}
void solve(){
    n=rd,q=rd;
    for(int i=1;i<=n;i++){
        f[i]=a[i]=i;sz[i]=col[i]=1;
        pre[i]=i-1;nxt[i]=i+1;
    }
    while(q--){
        int op=rd,x=rd;
        if(op==2){
            write(col[x]),Endl;
            continue;
        }
        int c=rd;
        x=find(x);
        col[a[x]]-=sz[x];
        a[x]=c;
        col[c]+=sz[x];
        pre[x]=find(pre[x]);
        nxt[x]=find(nxt[x]);
        if(pre[x]&&a[pre[x]]==c){
            f[pre[x]]=x;
            sz[x]+=sz[pre[x]];
            pre[x]=pre[pre[x]];
        }
        if(nxt[x]<=n&&a[nxt[x]]==c){
            f[nxt[x]]=x;
            sz[x]+=sz[nxt[x]];
            nxt[x]=nxt[nxt[x]];
        }
    }
}
signed main(){
    int T=1;
//  T=read<signed>();
    while(T--){
        solve();
    }
    return 0;
}