社区讨论

数据疑似可偷（指可撤销并查集）

jjodio9
P3206[HNOI2010] 城市建设参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mlrqj5o9
此快照首次捕获于
2026/02/18 15:53
20 小时前
此快照最后确认于
2026/02/19 12:16
2 分钟前
查看原帖
洛谷题解区诸位大佬的题解中的可撤销并查集都使用了按秩合并（按子树大小），这个复杂度是正确的。但是本蒟蒻使出乱做大法记录了每次路径压缩和合并操作的父节点和子节点并进行回溯。虽然本人非常地蒟蒻而且唐得要命，但是我认为我的判断是正确的：这种做法在遇到一次撤销操作时可能会把路径压缩中的一整个路径都撤销，时间复杂度是假的。不过这个做法非常难卡，因为数据要确保在 CDQ 分治的分治操作中多次卡 O(N)O(N) ，而 CDQ 分治会将边的顺序更改或者是将某些边优化掉 （就算能卡至少现在没卡）。
以下是某份唐人 AC 代码，使用了连 oi-wiki 都不敢记载的路径压缩可撤销并查集
以蒟蒻的看法，这个似乎是假的？CPP
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mid (ql+qr>>1)
#define enter putchar_unlocked('\n')
int n,m,q,back[2000005],top,son[2000005],fa[20005],u[50005],v[50005],w[50005],k[50005],d[50005],a[2000005],b[2000005],op[2000005],tmp;
long long ans[50005];
bool vis[50005];
il int getfa(int x){
    if(fa[x]^x)back[++top]=fa[x],son[top]=x,fa[x]=getfa(fa[x]);
    return fa[x];
}
il bool merge(int x,int y){
    x=getfa(x),y=getfa(y);
    if(x^y)back[++top]=fa[x],son[top]=x,fa[x]=y;
    return (bool)(x^y);
}
il void rtn(int ti){for(;top>ti;--top)fa[son[top]]=back[top];}
il bool cmp(const int&x,const int&y){return w[x]<w[y];}
void cdq(int ql,int qr,int ml,int mr){
    re int tm=top,kr=mr,cnt=0;
    if(ql==qr){
        tmp=w[k[ql]],w[k[ql]]=d[ql];
        for(re int i=ml;i<=mr;++i)a[++cnt]=b[i];
        sort(a+1,a+cnt+1,cmp);
        for(re int i=1;i<=cnt;++i)if(merge(u[a[i]],v[a[i]]))ans[ql]+=w[a[i]];
        rtn(tm),w[k[ql]]=tmp;return;
    }
    for(re int i=ql;i<=qr;++i)vis[k[i]]=1;
    for(re int i=ml;i<=mr;++i)if(!vis[b[i]])a[++cnt]=b[i];
    sort(a+1,a+cnt+1,cmp);
    for(re int i=ql;i<=qr;++i)merge(u[k[i]],v[k[i]]);
    for(re int i=1;i<=cnt;++i)op[i]=merge(u[a[i]],v[a[i]]);rtn(tm);
    for(re int i=1;i<=cnt;++i)op[i]=merge(u[a[i]],v[a[i]])?op[i]:2;rtn(tm);
    long long cost=0;int ntm;
    for(re int i=1;i<=cnt;++i)
        if(!op[i])b[++mr]=a[i];
        else if(op[i]&1)merge(u[a[i]],v[a[i]]),cost+=w[a[i]];
    for(re int i=ql;i<=qr;++i)vis[b[++mr]=k[i]]=0;
    ntm=top;
    cdq(ql,mid,kr+1,mr);
    for(re int i=ql;i<=mid;++i)w[k[i]]=d[i];rtn(ntm);
    cdq(mid+1,qr,kr+1,mr);rtn(ntm);
    for(re int i=ql;i<=qr;++i)ans[i]+=cost;
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(long long x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[50],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
signed main(){
    n=read(),m=read(),q=read();
    for(re int i=1;i<=m;++i)u[i]=read(),v[i]=read(),w[i]=read(),b[i]=i;
    for(re int i=1;i<=q;++i)k[i]=read(),d[i]=read();
    for(re int i=1;i<=n;++i)fa[i]=i;
    cdq(1,q,1,m);
    for(re int i=1;i<=q;++i)write(ans[i]),enter;
    return 0;
}
以下是按秩合并：
虽然操作更多，但是更快了CPP
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define mid (ql+qr>>1)
#define enter putchar_unlocked('\n')
int n,m,q,back[2000005],top,son[2000005],sz[200005],fa[20005],u[50005],v[50005],w[50005],k[50005],d[50005],a[2000005],b[2000005],op[2000005],tmp;
long long ans[50005];
bool vis[50005];
il int getfa(int x){return (fa[x]^x)?getfa(fa[x]):x;}
il bool merge(int x,int y){
    x=getfa(x),y=getfa(y);
    if(x^y){
        if(sz[x]<sz[y])x^=y^=x^=y;
        back[++top]=x,son[top]=y,fa[y]=x,sz[x]+=sz[y];
    }
    return (bool)(x^y);
}
il void rtn(int ti){for(;top>ti;--top)fa[son[top]]=son[top],sz[back[top]]-=sz[son[top]];}
il bool cmp(const int&x,const int&y){return w[x]<w[y];}
void cdq(int ql,int qr,int ml,int mr){
    re int tm=top,kr=mr,cnt=0;
    if(ql==qr){
        tmp=w[k[ql]],w[k[ql]]=d[ql];
        for(re int i=ml;i<=mr;++i)a[++cnt]=b[i];
        sort(a+1,a+cnt+1,cmp);
        for(re int i=1;i<=cnt;++i)if(merge(u[a[i]],v[a[i]]))ans[ql]+=w[a[i]];
        rtn(tm),w[k[ql]]=tmp;return;
    }
    for(re int i=ql;i<=qr;++i)vis[k[i]]=1;
    for(re int i=ml;i<=mr;++i)if(!vis[b[i]])a[++cnt]=b[i];
    sort(a+1,a+cnt+1,cmp);
    for(re int i=ql;i<=qr;++i)merge(u[k[i]],v[k[i]]);
    for(re int i=1;i<=cnt;++i)op[i]=merge(u[a[i]],v[a[i]]);rtn(tm);
    for(re int i=1;i<=cnt;++i)op[i]=merge(u[a[i]],v[a[i]])?op[i]:2;rtn(tm);
    long long cost=0;int ntm;
    for(re int i=1;i<=cnt;++i)
        if(!op[i])b[++mr]=a[i];
        else if(op[i]&1)merge(u[a[i]],v[a[i]]),cost+=w[a[i]];
    for(re int i=ql;i<=qr;++i)vis[b[++mr]=k[i]]=0;
    ntm=top;
    cdq(ql,mid,kr+1,mr);
    for(re int i=ql;i<=mid;++i)w[k[i]]=d[i];rtn(ntm);
    cdq(mid+1,qr,kr+1,mr);rtn(ntm);
    for(re int i=ql;i<=qr;++i)ans[i]+=cost;
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(long long x){
    x<0?x=-x,putchar_unlocked('-'):0;static short st[50],top(0);
    do st[++top]=x%10,x/=10;while(x);
    while(top)putchar_unlocked(st[top--]|48);
}
signed main(){
    n=read(),m=read(),q=read();
    for(re int i=1;i<=m;++i)u[i]=read(),v[i]=read(),w[i]=read(),b[i]=i;
    for(re int i=1;i<=q;++i)k[i]=read(),d[i]=read();
    for(re int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    cdq(1,q,1,m);
    for(re int i=1;i<=q;++i)write(ans[i]),enter;
    return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...