线段树合并[学习笔记]

news/发布时间2024/5/20 14:17:38

线段树合并

壹.

什么是线段树合并？ ~~简单来说就是合并两棵线段树~~

对于当前要合并的节点 $x,y$

如果一方为空返回另一方
否则分别合并左右子树

int merge(int x,int y){if(!x||!y)  return x+y;cnt(x)+=cnt(y);//...ls(x)=merge(ls(x),ls(y));rs(x)=merge(rs(x),rs(y));return x;
}

有时候需要到叶子结点再合并，然后 $pushup$

int merge(int x,int y,int l,int r){if(!x||!y)  return x+y;if(l==r){cnt(x)+=cnt(y);//...return x;}int mid=(l+r)>>1;ls(x)=merge(ls(x),ls(y),l,mid);rs(x)=merge(rs(x),rs(y),mid+1,r);pushup(x);return x;
}

大概就是这样。

我们多数情况是在动态开点线段树中使用线段树合并，动态开点，~~就是非静态地开一些点，~~ 就是一棵缺胳膊少腿的线段树，我们需要用哪个节点，再现开，很节省空间。、

嗯，很是简单，对吧，但是——

线段树合并题的难点从来不在线段树合并上(我口胡的)

贰.$hs$题单

$T_A$ 雨天的尾巴

假板子。

对于暴力做法是开 $O(N\times num)$ 的数组存每个节点存的每个物品的个数，最后每个点 $O(num)$ 遍历求答案。这无疑会浪费很多时间空间，那么动态开点权值线段树就是处理这种情况的有力武器( $num$ 为物品种数)

那么树上差分，最后跑子树求和的时候把子节点合并到父亲上，$pushup$ 统计答案。

！！！警示后人

线段树合并要"及时行乐"，合并完当前节点就赶紧存储答案，因为把它往上合并时他的信息会发生改变，因为 if(!x||!y) return x+y;，我在这卡了半天，不要到最后再输出每个节点的答案。

$CODE$

#include<bits/stdc++.h>
using namespace std;
#define read read()
#define pt puts("")
#define swap(x,y) (x^=y,y^=x,x^=y)
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
const int N = 1e5+10;
int n,m;
int ans[N];
int qu[N],qv[N],z[N],num;
int lsh[N];
namespace GETLCA{struct EDGE{int next,to;}e[N<<1];int head[N],tot;void add(int u,int v){e[++tot]={head[u],v};head[u]=tot;}int fa[N][18],depth[N];int lg2[N];void dfs(int x){depth[x]=depth[fa[x][0]]+1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x][0])  continue;fa[y][0]=x;dfs(y);}}void init(){for(int i=2;i<=n;i++)  lg2[i]=lg2[i>>1]+1;for(int j=1;j<=lg2[n];j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];}int LCA(int u,int v){if(depth[u]<depth[v])  swap(u,v);int k=lg2[depth[u]-depth[v]];for(int i=k;i>=0;i--)if(depth[fa[u][i]]>=depth[v])  u=fa[u][i];if(u==v)  return u;k=lg2[depth[u]];for(int i=k;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];return fa[u][0];}
}using namespace GETLCA;namespace Segment_Tree{struct Tree{int ls,rs,cnt,id;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define cnt(i) tr[i].cnt#define id(i) tr[i].id}tr[5000000];int root[N];int sum;void pushup(int i){cnt(i)=max(cnt(ls(i)),cnt(rs(i)));id(i)=cnt(ls(i))>=cnt(rs(i))?id(ls(i)):id(rs(i));}void create(int &i,int l,int r,int x,int k){if(!i) i=++sum;if(l==r){cnt(i)+=k;id(i)=cnt(i)?l:0;return;}int mid=(l+r)>>1;if(x<=mid)  create(ls(i),l,mid,x,k);else  create(rs(i),mid+1,r,x,k);pushup(i);}int merge(int x,int y,int l,int r){if(!x||!y)  return x+y;if(l==r){cnt(x)+=cnt(y);id(x)=cnt(x)?l:0;return x;}int mid=(l+r)>>1;ls(x)=merge(ls(x),ls(y),l,mid);rs(x)=merge(rs(x),rs(y),mid+1,r);pushup(x);return x;}void solve(int x){for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x][0])  continue;solve(y);root[x]=merge(root[x],root[y],1,num);}ans[x]=id(root[x]);//及时存答案！}
}using namespace Segment_Tree;
signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int i=1,a,b;i<n;i++){a=read,b=read;add(a,b);add(b,a);}dfs(1);init();for(int i=1;i<=m;i++)  qu[i]=read,qv[i]=read,lsh[i]=z[i]=read;sort(lsh+1,lsh+m+1);num=unique(lsh+1,lsh+m+1)-lsh-1;for(int i=1;i<=m;i++)  z[i]=lower_bound(lsh+1,lsh+num+1,z[i])-lsh;for(int i=1;i<=m;i++){int u=qu[i],v=qv[i];int lca=LCA(u,v);create(root[u],1,num,z[i],1);create(root[v],1,num,z[i],1);create(root[lca],1,num,z[i],-1);create(root[fa[lca][0]],1,num,z[i],-1);}solve(1);for(int i=1;i<=n;i++)  write(lsh[ans[i]]),pt;return 0;
}

$T_B$ bzoj4636蒟蒻的数列

值域很大，考虑动态开点，然后从左右儿子更新答案，貌似不用线段树合并

$CODE$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 40010
#define m 1000000000
int n;
int ans;
namespace SegmentTree{struct Tree{int ls,rs,k;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define k(i) tr[i].k}tr[10000000];int root;int tot;void create(int &i,int l,int r,int L,int R,int k){if(l>R||r<L)  return;if(!i)  i=++tot;if(L<=l&&r<=R){k(i)=max(k(i),k);return;}int mid=(l+r)>>1;create(ls(i),l,mid,L,R,k);create(rs(i),mid+1,r,L,R,k);return;}void query(int i,int l,int r){int mid=(l+r)>>1;if(!ls(i))  ans+=(mid-l+1)*k(i);if(!rs(i))  ans+=(r-mid)*k(i);if(ls(i))  k(ls(i))=max(k(ls(i)),k(i));if(rs(i))  k(rs(i))=max(k(rs(i)),k(i));if(ls(i))  query(ls(i),l,mid);if(rs(i))  query(rs(i),mid+1,r);return;}
}using namespace SegmentTree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;int l,r,k;for(int i=1;i<=n;i++){l=read,r=read-1,k=read;if(l>r)  continue;create(root,1,m,l,r,k);}query(root,1,m);write(ans);return 0;
}

$T_C$ Promotion Counting

这才是真板子。

每个节点开一棵权值线段树，从下往上合并，查询比该节点的能力值大的牛个数即可。

$CODE$

#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x)
{if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 100010
int n;
int p[N];
int t[N];
void LSH(){sort(t+1,t+n+1);int tt=unique(t+1,t+n+1)-t-1;for(int i=1;i<=n;i++)p[i]=lower_bound(t+1,t+tt+1,p[i])-t;
}struct Edge{int next,to;}e[N<<1];
int tot,head[N];
void add(int u,int v){e[++tot]={head[u],v};head[u]=tot;
}
int ans[N];
namespace SegmentTree{int sum;int root[N];struct Tree{int ls,rs;int L,R;int pro;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define L(i) tr[i].L#define R(i) tr[i].R#define pro(i) tr[i].pro}tr[100000000];void create(int &rt,int x,int l,int r){if(!rt)  rt=++sum;L(rt)=l,R(rt)=r;if(l==r){pro(rt)=1;return;}int mid=(l+r)>>1;if(x<=mid)  create(ls(rt),x,l,mid);else  create(rs(rt),x,mid+1,r);pro(rt)=pro(ls(rt))+pro(rs(rt));}int merge(int x,int y){if(!x||!y)  return x+y;pro(x)+=pro(y);ls(x)=merge(ls(x),ls(y));rs(x)=merge(rs(x),rs(y));return x;}int ask(int rt,int l,int r){if(!rt)  return 0;if(l<=L(rt)&&R(rt)<=r)  return pro(rt);int res=0,mid=(L(rt)+R(rt))>>1;if(l<=mid)  res+=ask(ls(rt),l,r);if(r>mid)  res+=ask(rs(rt),l,r);return res;}void dfs(int x){for(int i=head[x];i;i=e[i].next){int y=e[i].to;dfs(y);root[x]=merge(root[x],root[y]);}ans[x]=ask(root[x],p[x]+1,n);}
}using namespace SegmentTree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;for(int i=1;i<=n;i++)  t[i]=p[i]=read;LSH();for(int i=1;i<=n;i++){create(root[i],p[i],1,n);}for(int v=2;v<=n;v++){int u=read;add(u,v);}dfs(1);for(int i=1;i<=n;i++)write(ans[i]),pt;return 0;
}

$T_D$ 永无乡

怎么判断两个岛的联通情况？并查集维护。

对于B操作，合并两个点所在并查集对应的权值线段树。
对于Q操作，查询该并查集内第 $k$ 大点，从节点 $i$ 出发(如果有解的话)：
- 如果 $ls(i)$ 的点数大于 $k$，则第 $k$ 大点一定在左子树内，递归查询。
- 否则就是在右子树。

$CODE$

#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 100010
int n,m;
int w[N],id[N];
int fa[N];
int find(int x){if(fa[x]==x)  return x;return fa[x]=find(fa[x]);
}
namespace SegmentTree{struct Tree{int ls,rs,son;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define son(i) tr[i].son}tr[10000000];int cnt;int root[N];void create(int &i,int l,int r,int x){if(!i) i=++cnt;++son(i);if(l==r)  return;int mid=(l+r)>>1;if(x<=mid)  create(ls(i),l,mid,x);else  create(rs(i),mid+1,r,x);return;}int merge(int x,int y){if(!x||!y)  return x+y;son(x)+=son(y);ls(x)=merge(ls(x),ls(y));rs(x)=merge(rs(x),rs(y));return x;}int ask(int i,int l,int r,int k){if(l==r)  return id[l];int mid=(l+r)>>1;if(son(ls(i))>=k)  return ask(ls(i),l,mid,k);else  return ask(rs(i),mid+1,r,k-son(ls(i)));}
}using namespace SegmentTree;void link(int x,int y){x=find(x);y=find(y);if(x==y)  return;root[x]=merge(root[x],root[y]);fa[y]=fa[x];
}
int ans;
signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int i=1;i<=n;i++){w[i]=read;id[w[i]]=i;fa[i]=i;create(root[i],1,n,w[i]);}for(int i=1,a,b;i<=m;i++)  a=read,b=read,link(a,b);int T=read,x,y,k;for(int t=1;t<=T;t++){char op=getchar();while(op!='Q'&&op!='B')op=getchar();if(op=='B')  x=read,y=read,link(x,y);else{x=read,k=read;x=find(x);if(son(root[x])<k)  puts("-1");else  write(ask(root[x],1,n,k)),pt;}}return 0;
}

$T_E$ 魔法少女LJJ

此题不难，但是很烦。

操作$1$，动态开点
操作$2$，并查集维护，线段树合并
操作$3$，从根节点出发，访问左右子树，如果 $mid<x$，那么左子树显然都要变成 $0$(可以直接把左儿子断掉，不用$pushdown$)，注意这是权值线段树，然后我们用 $sum$ 记录有多少个点被赋值为 $0$，再将 $x$ 处 $update$ 即可。
操作$4$，同上。
操作$5$，类似永无乡。
操作$6$，小技巧，将 $a\times b$ 转化为 $log_2(a\times b)=log_2(a)+log_2(b)$，就不会爆了，值域缩小。但是注意开 $double$。
操作$7$，直接查询。
操作$8、9$，线段树分裂(口胡)，我们注意到 $c\leq 7$，出题人无意义行为 $\dots$

$CODE$

#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
const int N=400010;
const int M=1e9+5;
int m,n;
int sum;
int fa[N];
int find(int x){return (fa[x]==x?x:(fa[x]=find(fa[x])));
}namespace Segment_Tree{struct Tree{int ls,rs,cnt;double lgsum;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define cnt(i) tr[i].cnt#define lgsum(i) tr[i].lgsum}tr[5000000];int rt[N];int tot;void pushup(int i){cnt(i)=cnt(ls(i))+cnt(rs(i));lgsum(i)=lgsum(ls(i))+lgsum(rs(i));}void create(int &i,int l,int r,int x){if(!i)  i=++tot;if(l==r){cnt(i)++;lgsum(i)=1.0*cnt(i)*log2(l);return;}int mid=(l+r)>>1;if(x<=mid)  create(ls(i),l,mid,x);else  create(rs(i),mid+1,r,x);pushup(i);return;}int merge(int x,int y,int l,int r){if(!x||!y)  return x+y;if(l==r){cnt(x)+=cnt(y);lgsum(x)=1.0*cnt(x)*log2(l);return x;}int mid=(l+r)>>1;ls(x)=merge(ls(x),ls(y),l,mid);rs(x)=merge(rs(x),rs(y),mid+1,r);pushup(x);return x;}void link(int a,int b){int A=find(a);int B=find(b);if(A==B)  return;rt[A]=merge(rt[A],rt[B],1,M);fa[B]=A;}void modify1(int i,int l,int r,int x){if(l==r)  return;int mid=(l+r)>>1;if(mid<x){sum+=cnt(ls(i));ls(i)=0;modify1(rs(i),mid+1,r,x);}else  modify1(ls(i),l,mid,x);pushup(i);}void modify2(int i,int l,int r,int x){if(l==r)  return;int mid=(l+r)>>1;if(mid>x){sum+=cnt(rs(i));rs(i)=0;modify2(ls(i),l,mid,x);}else  modify2(rs(i),mid+1,r,x);pushup(i);}void update(int &i,int l,int r,int x){if(!i)  i=++tot;if(l==r){cnt(i)+=sum;lgsum(i)=1.0*cnt(i)*log2(x);return;}int mid=(l+r)>>1;if(x<=mid)  update(ls(i),l,mid,x);else  update(rs(i),mid+1,r,x);pushup(i);}int ask(int i,int l,int r,int k){if(l==r)  return l;int mid=(l+r)>>1;if(k<=cnt(ls(i)))  return ask(ls(i),l,mid,k);return  ask(rs(i),mid+1,r,k-cnt(ls(i)));}}using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifm=read;for(int i=1;i<=m;i++)  fa[i]=i;int op,x,a,b,k;for(int i=1;i<=m;i++){op=read;switch(op){case 1:x=read;create(rt[++n],1,M,x);break;case 2:a=read,b=read;link(a,b);break;case 3:a=read,x=read;a=find(a);sum=0;modify1(rt[a],1,M,x);update(rt[a],1,M,x);break;case 4:a=read,x=read;a=find(a);sum=0;modify2(rt[a],1,M,x);update(rt[a],1,M,x);break;case 5:a=read,k=read;a=find(a);write(ask(rt[a],1,M,k)),pt;break;case 6:a=read,b=read;a=find(a),b=find(b);puts(lgsum(rt[a])>lgsum(rt[b])?"1":"0");break;case 7:a=read;a=find(a);write(cnt(rt[a])),pt;break;default:break;}}return 0;
}

$T_F$ 大根堆

$DP$题，先跑dfs到叶子节点，向上合并时判断是否选父节点，然后线段树上跑二分确定最大值域。

$CODE$

#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 200010
int n;
int v[N],fa[N];
int vv[N],num;
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}namespace Segment_Tree{struct{int ls,rs,cnt;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define cnt(i) tr[i].cnt}tr[5000000];int rt[N],tot;void create(int &i,int l,int r,int L,int R){if(!i)  i=++tot;if(L<=l&&r<=R){cnt(i)++;return;}int mid=(l+r)>>1;if(mid>=L)  create(ls(i),l,mid,L,R);if(mid<R)  create(rs(i),mid+1,r,L,R);return;}int merge(int x,int y,int l,int r){if(cnt(x)<cnt(y))  swap(x,y);if(!x||!y)  return x+y;cnt(x)+=cnt(y);int mid=(l+r)>>1;ls(x)=merge(ls(x),ls(y),l,mid);rs(x)=merge(rs(x),rs(y),mid+1,r);return x;}int ask(int i,int l,int r,int k){if(!i)  return 0;int mid=(l+r)>>1;int res=cnt(i);if(k<=mid)  res+=ask(ls(i),l,mid,k);else  res+=ask(rs(i),mid+1,r,k);return res;}void dfs(int x){for(int i=head[x];i;i=e[i].next){int y=e[i].to;dfs(y);rt[x]=merge(rt[x],rt[y],1,num);}int ans1=ask(rt[x],1,num,v[x]-1)+1;int ans2=ask(rt[x],1,num,v[x]);if(ans1<=ans2)  return;int l=v[x],r=num,pos=v[x];while(l<=r){int mid=(l+r)>>1;if(ask(rt[x],1,num,mid)<ans1){l=mid+1;pos=mid;}else  r=mid-1;}create(rt[x],1,num,v[x],pos);return;}
}using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;for(int i=1;i<=n;i++){vv[i]=v[i]=read,fa[i]=read;if(fa[i])  add(fa[i],i);}sort(vv+1,vv+n+1);num=unique(vv+1,vv+n+1)-vv-1;for(int i=1;i<=n;i++)  v[i]=lower_bound(vv+1,vv+num+1,v[i])-vv;dfs(1);write(ask(rt[1],1,num,num));return 0;
}

$T_G$ 领导集团问题

上题多倍经验，贺了 $shadow$ 的 $muiltiset$ 做法，比我的做法快了 $3$ 倍。

https://www.cnblogs.com/The-Shadow-Dragon/p/18169047

$CODE$

#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 200010
int n;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
multiset<int>s[N];
multiset<int>::iterator it;void merge(int x,int y){if(s[x].size()<s[y].size())  swap(s[x],s[y]);for(it=s[y].begin();it!=s[y].end();++it)s[x].insert(*it);s[y].clear();
}
void dfs(int x){for(int i=head[x];i;i=e[i].next){int y=e[i].to;dfs(y);merge(x,y);}s[x].insert(w[x]);it=s[x].lower_bound(w[x]);if(it!=s[x].begin())s[x].erase(--it);return;
}signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;for(int i=1;i<=n;i++)  w[i]=read;int fa;for(int i=2;i<=n;i++)  fa=read,add(fa,i);dfs(1);write(s[1].size());return 0;
}

$T_H$ 大融合

离线建树操作，跑 $DFS$ 序。

根据 $DFS$ 序建权值线段树，并查集维护连通状态。(未完)

$CODE$

#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
#define int long long
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 100010
int n,m;
struct operate{int op,u,v;
}q[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}
bool exis[N];
int dfn[N],t;
int depth[N];
int out[N];
int id[N<<1];void get_dfn(int x,int pre){depth[x]=depth[pre]+1;dfn[x]=++t;id[t]=x;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==pre)  continue;get_dfn(y,x);}out[x]=t;
}int fa[N];
int find(int x){return (fa[x]==x?x:(fa[x]=find(fa[x])));}namespace Segment_Tree{struct Tree{int ls,rs,cnt;#define ls(i) tr[i].ls#define rs(i) tr[i].rs#define cnt(i) tr[i].cnt}tr[5000000];int rt[N],tot;void pushup(int i){cnt(i)=cnt(ls(i))+cnt(rs(i));}void create(int &i,int l,int r,int x){if(!i)  i=++tot;if(l==r){cnt(i)++;return;}int mid=(l+r)>>1;if(x<=mid)  create(ls(i),l,mid,x);else  create(rs(i),mid+1,r,x);pushup(i);return;}int merge(int x,int y,int l,int r){if(!x||!y) return x|y;if(l==r){cnt(x)+=cnt(y);return x;}int mid=(l+r)>>1;ls(x)=merge(ls(x),ls(y),l,mid);rs(x)=merge(rs(x),rs(y),mid+1,r);pushup(x);return x;}int query(int i,int l,int r,int ql,int qr){if(!i)  return 0;if(ql<=l&&r<=qr)  return cnt(i);int mid=(l+r)>>1;int res=0;if(ql<=mid)  res+=query(ls(i),l,mid,ql,qr);if(qr>mid)  res+=query(rs(i),mid+1,r,ql,qr);return res; }
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int i=1;i<=n;i++)  fa[i]=i;for(int i=1;i<=m;i++){char c=getchar();while(c!='A'&&c!='Q') c=getchar();q[i].op=(c=='A'?0:1);q[i].u=read,q[i].v=read;exis[q[i].u]=exis[q[i].v]=1;if(c=='A')  add(q[i].u,q[i].v),add(q[i].v,q[i].u);}for(int i=1;i<=n;i++){if(!exis[i])  continue;if(!dfn[i]){// add(0,i),add(i,0);depth[i]=1;get_dfn(i,0);}}for(int i=1;i<=n;i++){create(rt[i],1,t,dfn[i]);}for(int i=1;i<=m;i++){int u=q[i].u,v=q[i].v;if(depth[v]<depth[u])  swap(u,v);int uu=find(u),vv=find(v);if(!q[i].op){rt[uu]=merge(rt[uu],rt[vv],1,t);fa[vv]=uu;}else{int sum=cnt(rt[uu]);int sumv=query(rt[uu],1,t,dfn[v],out[v]);int sumu=sum-sumv;write(sumu*sumv);pt;}}return 0;
}