记录编号	412492	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的重心	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.315 s
提交时间	2017-06-09 16:24:12	内存使用	10.59 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,fa[N],s[N],son[N][2],v[N],pre[N],suf[N],prev[N],next[N];
bool root[N];
int apre[N],asuf[N];bool rev[N];
//v[x]表示子树x大小减去pre_child子树的大小 
//pre,suf表示一颗splay上v的前缀后缀和 
#define lc son[x][0]
#define rc son[x][1]
void flip(int x){
	swap(lc,rc);
	swap(prev[x],next[x]);
	swap(pre[x],suf[x]);
	swap(apre[x],asuf[x]);
	rev[x]^=1;
}
void add_pre(int x,int d){
	pre[x]+=d;
	apre[x]+=d;
}
void add_suf(int x,int d){
	suf[x]+=d;
	asuf[x]+=d;
}
void update(int x){
	s[x]=s[lc]+s[rc]+1;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (apre[x]){
		if (lc) add_pre(lc,apre[x]);
		if (rc) add_pre(rc,apre[x]);
		apre[x]=0;
	}
	if (asuf[x]){
		if (lc) add_suf(lc,asuf[x]);
		if (rc) add_suf(rc,asuf[x]);
		asuf[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!root[y]) rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
//suf[x]即子树x的大小 
int top(int x){
	for (;;x=lc){
		pushdown(x);
		if (!lc) break;
	}
	splay(x);
	return x;
}
void link_r(int x,int y){
	y=top(y);
	next[x]=y;
	prev[y]=x;
	v[x]-=suf[y];
	pre[x]-=suf[y];
	add_pre(y,pre[x]);
	root[rc=y]=0;
	update(x);
}
void cut_r(int x){
	int y=rc;
	if (!y) return;
	root[rc]=1;rc=0;
	update(x);
	y=top(y);
	next[x]=prev[y]=0;
	add_pre(y,-pre[x]);
	v[x]+=suf[y];
	pre[x]+=suf[y];
}
void access(int x){
	splay(x);
	cut_r(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		cut_r(y);
		link_r(y,x);
		splay(x);
	}
}
void makeroot(int x){
	access(x);
	flip(x);
}
int T[N],size[N],ans;
int find(int x){return T[x]==x?x:T[x]=find(T[x]);}
int find(int x,int R){
	if (R>s[x]) return 0;
	while (1){
		pushdown(x);
		int i=s[lc]+1;
		if (R==i) break;
		if (R>i) R-=i,x=rc;else x=lc;
	}
	splay(x);
	return x;
}
int getsize(int x){
	if (!x) return 0;
	splay(x);
	return suf[x];
}
void solve(int x,int l,int r,int size){
	int mid=(l+r)>>1,pl=find(x,mid),pr=find(pl,mid+1);
	int sl=getsize(pl),sr=getsize(pr);
	if (sl*2>=size&&sr*2<=size) ans=min(ans,pl);
	if (l==r) return;
	if (sr*2<size) solve(pr,l,mid,size);
	if (sl*2>size) solve(pr,mid+1,r,size);
}
int main()
{
	freopen("G_Tree.in","r",stdin);
	freopen("G_Tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	int xor_sum=0;
	for (int i=1;i<=n;i++){
		pre[i]=suf[i]=v[i]=size[i]=s[i]=root[i]=1;
		T[i]=i;
		xor_sum^=i;
	}
	char tp[10];int x,y;
	while (m--){
		scanf("%s",tp);
		if (tp[0]=='X') printf("%d\n",xor_sum);
		if (tp[0]=='Q'){
			scanf("%d",&x);
			printf("%d\n",find(x));
		}
		if (tp[0]=='A'){
			scanf("%d%d",&x,&y);
			int a=find(x),b=find(y);
			if (size[a]>size[b]) swap(x,y),swap(a,b);
			xor_sum^=a;
			xor_sum^=b;
			makeroot(y);
			fa[y]=x;
			access(x);
			v[x]+=suf[y];
			pre[x]+=suf[y];
			add_suf(x,suf[y]);
			makeroot(a);
			access(b);
			ans=n+1;
			solve(b,1,s[b],size[a]+size[b]);
			//getroot(b,size[a]+size[b]);
			//printf("new root is %d\n",ans);
			T[a]=T[b]=T[ans]=ans;
			size[ans]=size[a]+size[b];
			xor_sum^=ans;
		}
	}
	return 0;
}