题解：P8123 [BalticOI 2021 Day1] Inside information
非常好的线段树合并题，这使我的 binzhou 旋转。
题目开始给了个很重要的信息，合并后形成一棵树，然后在加上共享数据这个神秘操作，自然想到合并线段树。
前两个操作非常板子，第三个操作非常不好处理。
我刚开始想的是合并时，把贡献在做一次合并，但是这样复杂度就退化了。
考虑把第三个询问独立出来，并且先建出图，给每个边赋上一个权值，权值的大小为合并的次数。
发现每个询问三能有贡献的点到询问的点的权值是单调递减的。
这玩意是不是还是非常像合并？没错，这玩意还能用线段树合并维护。我们倒着建图，保证新建的边的点的新增贡献等于询问中另一点的能到的所有点。这样子合并的值就很好算了。
然后对于每个点再来一颗线段树维护他能走到的边，能走当且仅当他走的路的权值单调递增。答案就是这玩意加一。
注意修改不能再原树上做，要新开节点，否则会影响和他共用一个根的点。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<vector>
#include<stdio.h>
#include<map>
#include<set>
#include<string.h>
#include<random>
#include<time.h>
#include<stdlib.h>
#include<bitset>
#define il inline
#define reg register
#define popcount __builtin_popcount
using namespace std;
inline void read(int &n){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}n=x*f;}
inline void print(int n){if(n<0){putchar('-');n*=-1;}if(n>9) print(n/10);putchar(n % 10 + '0');}
const int N=1.6e6,M=3.5e7;
int n,m,tree[M],ls[M],rs[M],tot,rt[N];
int update(int x,int l,int r,int pos,int w){
if(l==r){
int tmp=++tot;tree[tmp]=tree[x]+w;return tmp;
}
int mid=(l+r)/2,tmp=++tot;
if(pos<=mid){
rs[tmp]=rs[x];
if(ls[x]==0)ls[x]=++tot;
ls[tmp]=update(ls[x],l,mid,pos,w);
}else{
ls[tmp]=ls[x];
if(rs[x]==0)rs[x]=++tot;
rs[tmp]=update(rs[x],mid+1,r,pos,w);
}tree[tmp]=tree[ls[tmp]]+tree[rs[tmp]];return tmp;
}
int query(int x,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r)return tree[x];
int mid=(l+r)/2,re=0;
if(ls[x]&&ql<=mid)re+=query(ls[x],l,mid,ql,qr);
if(rs[x]&&qr>mid)re+=query(rs[x],mid+1,r,ql,qr);
return re;
}
int merge(int x1,int x2,int l,int r){
if(x1==0||x2==0){
return x1+x2;
}
if(l==r){
int tmp=++tot;tree[tmp]=tree[x1]+tree[x2];return tmp;
}
int mid=(l+r)/2;
int tmp=++tot;
ls[tmp]=merge(ls[x1],ls[x2],l,mid);rs[tmp]=merge(rs[x1],rs[x2],mid+1,r);
tree[tmp]=tree[ls[tmp]]+tree[rs[tmp]];return tmp;
}
char cc[N];int ll[N],rr[N];
int main(){
read(n);read(m);
rt[0]=++tot;
for(int i=1;i<=n;i++){
rt[i]=++tot;rt[i]=update(rt[i],1,n,i,1);
}
for(int i=1;i<=n;i++){
rt[i+n]=++tot;
}
for(int lll=1;lll<=n+m-1;lll++){
cin>>cc[lll];
if(cc[lll]=='S'){
read(ll[lll]);read(rr[lll]);
}else if(cc[lll]=='Q'){
read(ll[lll]);read(rr[lll]);
}else{
read(ll[lll]);
}
}
int cnt=n-1;
for(int lll=n+m+1;lll>=1;lll--){
if(cc[lll]=='S'){
int l=ll[lll],r=rr[lll];
l=rt[l+n];r=rt[r+n];
rt[ll[lll]+n]=update(l,1,n-1,cnt,1);rt[rr[lll]+n]=merge(r,rt[ll[lll]+n],1,n-1);
rt[ll[lll]+n]=rt[rr[lll]+n];cnt--;
}
}
for(int lll=1;lll<=n+m-1;lll++){
char c=cc[lll];
if(c=='S'){
int l=ll[lll],r=rr[lll];
rt[l]=merge(rt[l],rt[r],1,n);rt[r]=rt[l];cnt++;
}else if(c=='Q'){
int l=ll[lll],r=rr[lll];
if(query(rt[l],1,n,r,r)==1)puts("yes");else puts("no");
}else{
int l=ll[lll];
printf("%d\n",query(rt[l+n],1,n-1,1,cnt)+1);
}
}
return 0;
}