传送门
题意简述：
要求支持以下操作：
在a与b之间连一条长度为i的边（i是操作编号）；删除当前图中边权最大的k条边；表示撤销第 i−1次操作，保证第1次，第i−1 次不是撤回操作。
要求在每次操作后输出当前图的最小生成树边权和。
思路：由于边权为当前操作编号因此相当于边是单调加入的，也就是说我们可以直接上kruskalkruskalkruskal的合并方法。
关键在于怎么维护这几个操作。
加边操作：加入一条边。
删除操作：删掉最近加入的kkk条边。
撤回加边操作：删掉最近加入的一条边
撤回删除操作：等于没有变化。
那么我们用栈存下每一个状态的值转移给后面的状态即可。
注意并查集要简单可持久化一下，可以用按秩合并。
实测了一波按sizesizesize合并比按深度合并快。
按sizesizesize合并代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=5e5+5;
int n,m,fa[N],siz[N],cnt[N],stk[N],top=0;
ll ans[N];
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
inline void print(int x){cout<<(cnt[x]==n-1?ans[x]:0)<<'\n';}
inline void add(int x,int y,int w){
int fx=find(x),fy=find(y);
++top,cnt[top]=cnt[top-1],ans[top]=ans[top-1];
if(fx==fy)stk[top]=0;
else{
if(siz[fx]<siz[fy])swap(fx,fy);
stk[top]=fy,fa[fy]=fx,siz[fx]+=siz[fy],++cnt[top],ans[top]+=w;
}
}
inline void delet(int tim){
while(tim--){
int p=stk[top--];
siz[fa[p]]-=siz[p],fa[p]=p;
}
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)fa[i]=i,siz[i]=1;
for(ri last=0,k,i=1;i<=m;++i){
char s[6];
scanf("%s",s);
if(s[0]=='A'){
if(last==2)delet(k);
int a=read(),b=read();
add(a,b,i),print(top),last=1;
}
else if(s[0]=='D'){
if(last==2)delet(k);
int a=read();
print(top-a),last=2,k=a;
}
else{
if(last==1)delet(1);
print(top),last=0;
}
}
return 0;
}
按深度合并代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=3e5+5,M=5e5+5;
int n,m,fa[N],rk[N],cnt[M],stk[M],top=0;
ll ans[M];
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
inline void print(int x){cout<<(cnt[x]==n-1?ans[x]:0)<<'\n';}
inline void add(int x,int y,int w){
int fx=find(x),fy=find(y);
++top,cnt[top]=cnt[top-1],ans[top]=ans[top-1];
if(fx==fy)stk[top]=0;
else{
if(rk[fx]<rk[fy])swap(fx,fy);
stk[top]=fy,fa[fy]=fx,rk[fx]+=rk[fx]==rk[fy],++cnt[top],ans[top]+=w;
}
}
inline void delet(int tim){
while(tim--){
int p=stk[top--];
rk[fa[p]]-=rk[fa[p]]==rk[p]+1,fa[p]=p;
}
}
int main(){
n=read(),m=read();
for(ri i=1;i<=n;++i)fa[i]=i,rk[i]=1;
for(ri last=0,k,i=1;i<=m;++i){
char s[6];
scanf("%s",s);
if(s[0]=='A'){
if(last==2)delet(k);
int a=read(),b=read();
add(a,b,i),print(top),last=1;
}
else if(s[0]=='D'){
if(last==2)delet(k);
int a=read();
print(top-a),last=2,k=a;
}
else{
if(last==1)delet(1);
print(top),last=0;
}
}
return 0;
}