题目链接：点击查看
题目大意：
题目分析：数据结构的题目写起来真好玩~（debug到吐）
考虑离线，题目实质上就是维护两个森林，然后对同一个序列进行的赋值操作，如果是对单一的森林进行加边删边然后连通块内求值修改之类的话，不难想到克鲁斯卡尔重构树，但两个森林的话该怎么办呢
注意到第一个森林中对连通块的操作是加法，第二个森林中对连通块的操作是置零
任取一个点 x 进行讨论，假设现在不考虑第二个森林的贡献，也就是忽略掉第二种操作和第四种操作，并且在每次操作后都记录一下点 x 的值，更具体的，设 val_x[ i ] 是在经过第 i 个操作后，点 x 的值
现在假设第 r 个操作是 “ Q x ”，也就是在第 r 个操作时需要输出 x 的值，但并不是需要输出 val_x[ r ] ，因为 val_x 记录的只是第一个森林的贡献，为了计算总贡献，我们需要知道在第 r 个操作之前，对于点 x 来说距离最近的一次操作 4，也就是第二个森林的置零操作，找到的这个位置记为 l，换句话说，现在在第 l 个操作时将点 x 置零，需要输出第 r 个操作时 x 的值，也就是说在闭区间 [ l + 1 , r ] 内 val_x 的值只受到了第一个森林的影响，到此为止不难想到答案就是 val_x[ r ] - val_x[ l ] 了
综上所述，我们将问题又进行了进一步的转换：
- 先通过第二个森林求出每一个操作 Q x 的可行区间 [ l , r ] ，满足：
- 当前的操作 Q x 是第 r 次操作
- 第 l 次操作是对于点 x 进行的置零操作
- 闭区间 [ l + 1 , r ] 内再无对于点 x 进行的置零操作
- 再通过第二个森林去维护每个点的 val_x，对于一个操作 Q x 来说，其通过上述操作求出的区间为 [ l , r ] ，那么在其 l 位置减去 val_x[ l ]，在其 r 位置减去 val_x[ r ] 就是操作 Q x 的答案
这样就将第一个森林和第二个森林各自的作用区分开来，转换成了两个独立的森林提供的贡献
剩下的用克鲁斯卡尔重构树乱搞就好了
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char op[N][2];int n,m,a[N];LL ans[N];vector<int>q[N];struct Ex_Kruskal
{int f[N],L[N],R[N],sz[N],tot,index;vector<int>node[N];void init(int n){tot=0;index=n;for(int i=0;i<=n<<1;i++)f[i]=i;}int find(int x){return f[x]==x?x:f[x]=find(f[x]);}void addedge(int x,int y){int xx=find(x),yy=find(y);if(xx!=yy){f[xx]=f[yy]=++index;node[index].push_back(xx);node[index].push_back(yy);}}void dfs(int u){L[u]=++tot;sz[u]=(u<=n);for(auto v:node[u]){dfs(v);sz[u]+=sz[v];}R[u]=tot;}
};struct Set1
{Ex_Kruskal kru;int n;struct Node{int l,r;LL sum;}tree[N<<2];void get_dfs(){n=kru.index;for(int i=1;i<=n;i++)if(kru.find(i)==i)kru.dfs(i);}void pushdown(int k){if(tree[k].sum){tree[k<<1].sum+=tree[k].sum;tree[k<<1|1].sum+=tree[k].sum;tree[k].sum=0;}}void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int l,int r,int val){if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].sum+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);}void change(int x){update(1,kru.L[a[x]],kru.R[a[x]],kru.sz[a[x]]);}LL query(int k,int pos){if(tree[k].l==tree[k].r)return tree[k].sum;pushdown(k);int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)return query(k<<1,pos);elsereturn query(k<<1|1,pos);}LL ask(int x){return query(1,kru.L[a[x]]);}
}t1;struct Set2
{Ex_Kruskal kru;int n;struct Node{int l,r;int time;}tree[N<<2];void get_dfs(){n=kru.index;for(int i=1;i<=n;i++)if(kru.find(i)==i)kru.dfs(i);}void pushdown(int k){if(tree[k].time){tree[k<<1].time=tree[k<<1|1].time=tree[k].time;tree[k].time=0;}}void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;tree[k].time=0;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int l,int r,int val){if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].time=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);}void change(int x){update(1,kru.L[a[x]],kru.R[a[x]],x);}int query(int k,int pos){if(tree[k].l==tree[k].r)return tree[k].time;pushdown(k);int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)return query(k<<1,pos);elsereturn query(k<<1|1,pos);}int ask(int x){return query(1,kru.L[a[x]]);}
}t2;int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d",&n,&m);t1.kru.init(n),t2.kru.init(n);for(int i=1,x,y;i<=m;i++){scanf("%s%d",op[i],&x);switch(op[i][0]){case 'U':scanf("%d",&y);t1.kru.addedge(x,y);break; case 'M':scanf("%d",&y);t2.kru.addedge(x,y);break;case 'A':a[i]=t1.kru.find(x);break;case 'Z':a[i]=t2.kru.find(x);break;case 'Q':a[i]=x;break;}}t1.get_dfs(),t2.get_dfs();t1.build(1,1,t1.n),t2.build(1,1,t2.n);for(int i=1;i<=m;i++){switch(op[i][0]){case 'Z':t2.change(i);break;case 'Q':q[t2.ask(i)].push_back(i);break;}}for(int i=1;i<=m;i++){switch(op[i][0]){case 'A':t1.change(i);break;case 'Z':for(auto it:q[i])ans[it]-=t1.ask(it);break;case 'Q':ans[i]+=t1.ask(i);break;}}for(int i=1;i<=m;i++)if(op[i][0]=='Q')printf("%lld\n",ans[i]);return 0;
}