题目的操作很特殊,所以就很简单。如果没有回退操作,那么就并查集按秩合并,可以删最近加的边。

注意到若回退操作前是加边操作,那么就相当于是删一条边。

如果回退操作前是删 \(k\) 条边的操作,暴力的话复杂度就炸了。

那么就离线,如果一个删 \(k\) 条边的操作后是回退,那么就不删,

答案是可以之前记下的,记 \(ans(m)\) 表示 边数是 \(m\) 时的答案。输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<algorithm>
typedef long long LL;
using namespace std;
const int maxn=1000005;
int n,m,Q;
struct Operation{
int typ,x,y;
} q[maxn];
struct data{
int x,fa_x,rk_x,y,fa_y,rk_y;
data(int t1=0,int t2=0,int t3=0,int t4=0,int t5=0,int t6=0)
:x(t1),fa_x(t2),rk_x(t3),y(t4),fa_y(t5),rk_y(t6){}
} b[maxn];
int fa[maxn],rk[maxn],cnt[maxn];
LL ans[maxn];
int getfa(int x){ return fa[x]==x?x:getfa(fa[x]); }
void Add(int x,int y,int z){
m++;
if(getfa(x)==getfa(y)){
ans[m]=ans[m-1]; cnt[m]=cnt[m-1];
b[m]=data(); return;
}
cnt[m]=cnt[m-1]-1; ans[m]=ans[m-1]+z;
x=getfa(x); y=getfa(y);
b[m]=data(x,fa[x],rk[x],y,fa[y],rk[y]);
if(rk[x]<rk[y]) swap(x,y);
fa[y]=x; if(rk[x]==rk[y]) rk[x]++;
}
void Delete(){
fa[b[m].x]=b[m].fa_x; rk[b[m].x]=b[m].rk_x;
fa[b[m].y]=b[m].fa_y; rk[b[m].y]=b[m].rk_y;
m--;
}
void Delete_k(int k){
while(k--) Delete();
}
int main(){
freopen("uoj14.in","r",stdin);
freopen("uoj14.out","w",stdout);
scanf("%d%d",&n,&Q);
for(int i=1;i<=Q;i++){
char st[10]; scanf("%s",st);
if(st[0]=='A') q[i].typ=1, scanf("%d%d",&q[i].x,&q[i].y);
else if(st[0]=='D') q[i].typ=2, scanf("%d",&q[i].x);
else q[i].typ=3;
}
for(int i=1;i<=n;i++) fa[i]=i; ans[0]=0; cnt[0]=n;
for(int i=1;i<=Q;i++){
if(q[i].typ==1) Add(q[i].x,q[i].y,i), printf("%lld\n",ans[m]*(cnt[m]==1));
if(q[i].typ==3) Delete(), printf("%lld\n",ans[m]*(cnt[m]==1));
if(q[i].typ==2){
if(q[i+1].typ!=3) Delete_k(q[i].x), printf("%lld\n",ans[m]*(cnt[m]==1));
if(q[i+1].typ==3){
printf("%lld\n%lld\n",ans[m-q[i].x]*(cnt[m-q[i].x]==1),ans[m]*(cnt[m]==1));
i++;
}
}
}
return 0;
}