题解：
正解是可持久化并查集
但这个显然是lct可以维护的
但这常数是个问题啊？？？
#include <bits/stdc++.h>
using namespace std;
struct re{
int a,b,c;
};
const int N=5e5;
int fa[N],ls[N],rs[N],v[N];
int cnt,last,last1,last2,n,m,ans;
bool rev[N];
deque<re> q1,q2;
void down(int x)
{
if (!rev[x]) return;
swap(ls[x],rs[x]);
rev[ls[x]]^=; rev[rs[x]]^=;
rev[x]=;
}
bool pd(int x)
{
if (ls[fa[x]]!=x&&rs[fa[x]]!=x) return();
else return ();
}
void rotate(int x,int y)
{
int fath=fa[x];
if (y==)
{
rs[fath]=ls[x];
if (ls[x]) fa[ls[x]]=fath;
} else
{
ls[fath]=rs[x];
if (rs[x]) fa[rs[x]]=fath;
}
fa[x]=fa[fath];
if (pd(fath))
{
if (ls[fa[x]]==fath) ls[fa[x]]=x;
else rs[fa[x]]=x;
}
fa[fath]=x;
if (y==) ls[x]=fath; else rs[x]=fath;
}
void dfs(int x)
{
if (pd(x)) dfs(fa[x]);
down(x);
}
void splay(int x)
{
dfs(x);
int fath=fa[x];
while (pd(x))
{
if (!pd(fa[x]))
{
if (x==ls[fa[x]]) rotate(x,);
else rotate(x,);
} else
{
if (ls[fa[fath]]==fath)
if (ls[fath]==x) rotate(fath,),rotate(x,);
else rotate(x,),rotate(x,);
else if (rs[fath]==x) rotate(fath,),rotate(x,);
else rotate(x,),rotate(x,);
}
fath=fa[x];
}
}
void access(int x)
{
for (int y=;x;y=x,x=fa[x])
{
splay(x); rs[x]=y;
}
}
void makeroot(int x)
{
access(x);
splay(x);
rev[x]^=;
}
int findroot(int x)
{
access(x);
splay(x);
while (ls[x]) x=ls[x];
return x;
}
bool find (int x,int y)
{
makeroot(x);
if (findroot(y)==x) return ;
else return ;
}
void link(int x,int y)
{
//**
//cout<<x<<" "<<y<<endl;
//**
makeroot(x);
fa[x]=y;
}
void cut(int x,int y)
{
makeroot(x);
access(y);
splay(y);
ls[y]=fa[x]=;
}
char c[];
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>n>>m;
for (int i=;i<=m;i++)
{
cin>>c;int x,y;
if (c[]=='A')
{
cin>>x>>y;
re a; a.a=x; a.b=y; a.c=i; q1.push_back(a);
if (!find(x,y))
{
cnt++; ans+=i;
link(x,i+n);
link(i+n,y);
v[i+n]=i;
}
last=; last1=x; last2=y;
}
if (c[]=='D')
{
last=;
cin>>x; q2.clear();
for (int i=;i<=x;i++)
{
re y=q1.back(); q1.pop_back(); q2.push_back(y);
if (find(y.a,y.c+n))
{
cut(y.a,y.c+n); cut(y.b,y.c+n);
cnt--; ans-=y.c;
}
}
}
if (c[]=='R')
{
if (last==)
{
if (find(last1,i-+n))
{
cut(last1,i-+n); cut(last2,i-+n);
cnt--; ans-=i-;
}
q1.pop_back();
} else
{
while (!q2.empty())
{
re x=q2.back(); q2.pop_back();
q1.push_back(x);
if (!find(x.a,x.b))
{
cnt++; ans+=x.c;
link(x.a,x.c+n);
link(x.b,x.c+n);
}
}
}
}
if (cnt==n-) cout<<ans; else cout<<;
cout<<endl;
}
return ;
}