树上主席树

#include<bits/stdc++.h>
using namespace std;

const int N=8e4+5;
int n,m,q,ans,a[N],s[N];
int f[N],dep[N],fa[N][15],siz[N];
int tt,root[N],ls[N*600],rs[N*600],vl[N*600];
vector<int>vv[N];

void build(int l,int r,int &p)
{
	p=++tt;
	if(l==r) return;
	int m=(l+r)>>1;
	build(l,m,ls[p]);
	build(m+1,r,rs[p]);
}

void insert(int l,int r,int x,int &p1,int p2)
{
	p1=++tt;
	
	if(l==r)
	{
		vl[p1]=vl[p2]+1;
		return;
	}
	
	int m=(l+r)>>1;
	
	if(x<=m) insert(l,m,x,ls[p1],ls[p2]),rs[p1]=rs[p2];
	else insert(m+1,r,x,rs[p1],rs[p2]),ls[p1]=ls[p2];
	
	vl[p1]=vl[ls[p1]]+vl[rs[p1]]; 
}

void dfs(int u,int x)
{
	siz[x]++;
	f[u]=x;
	
	insert(1,s[0],a[u],root[u],root[fa[u][0]]);
	
	for(int i=0;i<vv[u].size();++i)
	{
		int v=vv[u][i];
		
		if(v==fa[u][0]) continue;
		
		dep[v]=dep[u]+1;
		fa[v][0]=u;
		for(int j=1;(1<<j)<=dep[v]&&j<=10;++j) fa[v][j]=fa[fa[v][j-1]][j-1];
		
		dfs(v,x);
	}
}

int lca_(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	
	for(int j=10;j>=0;--j)
	if(dep[y]+(1<<j)<=dep[x]) x=fa[x][j];
	
	if(x==y) return x;
	
	for(int j=10;j>=0;--j)
	if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
	
	return fa[x][0];
}

int query(int l,int r,int k,int p1,int p2,int p3,int p4)
{
	if(l==r) return s[l];
	
	int m=(l+r)/2,val=vl[ls[p1]]+vl[ls[p2]]-vl[ls[p3]]-vl[ls[p4]];
	
	if(k<=val) return query(l,m,k,ls[p1],ls[p2],ls[p3],ls[p4]);
	else return query(m+1,r,k-val,rs[p1],rs[p2],rs[p3],rs[p4]);
}

int find(int x)
{
	return f[x]!=x?f[x]=find(f[x]):x;
}

int main()
{
	scanf("%d %d %d %d",&n,&n,&m,&q);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),s[i]=a[i];
	
	sort(s+1,s+n+1);
	s[0]=unique(s+1,s+n+1)-s-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(s+1,s+s[0]+1,a[i])-s;
	
	build(1,s[0],root[0]);
	
	for(int i=1,u,v;i<=m;++i)
	{
		scanf("%d %d",&u,&v);
		vv[u].push_back(v);
		vv[v].push_back(u);
	}
	
	for(int i=1;i<=n;++i)
	if(!root[i]) dfs(i,i);

	char op[3];
	for(int i=1,x,y,k;i<=q;++i)
	{
		scanf("%s",&op);
		scanf("%d %d",&x,&y);
		
		x^=ans;
		y^=ans;
		
		if(op[0]=='Q')
		{
			scanf("%d",&k);
			k^=ans;
			
			int lca=lca_(x,y);
			ans=query(1,s[0],k,root[x],root[y],root[lca],root[fa[lca][0]]);
			printf("%d\n",ans);
		}
		else
		{
			vv[y].push_back(x);
			vv[x].push_back(y);
			
			int xx=find(x),yy=find(y);
//			if(xx==yy) continue;
			//保证siz[xx]<siz[yy]
			
			if(siz[xx]>siz[yy]) swap(xx,yy),swap(x,y);
			
			fa[x][0]=y;
			dep[x]=dep[y]+1;
			for(int j=1;(1<<j)<=dep[x]&&j<=10;++j) fa[x][j]=fa[fa[x][j-1]][j-1];

			dfs(x,yy);
		}
	}
}

除了第一个点全部RE，落泪了