自动搬运

查看原文

来自洛谷，原作者为

	suzhikz 我永远喜欢艾莉丝！

搬运于2025-08-24 22:36:13，当前版本为作者最后更新于2025-01-01 22:16:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常好的线段树合并题，这使我的 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;
}