题目传送门

这份代码的 tr[] 数组现在会RE #2 #3 #6 ，开到 500N 可以过#2 ，同时#3 #6 MLE，初步怀疑是代码出现了浪费空间等问题

做法为 主席树+启发式合并，求调玄关

#include<bits/stdc++.h>
using namespace std;
const int N=8e4+5;
int n,m,q,len,id,ans,tim,testcase;
int a[N],lsh[N],dep[N],fa[N][17],rt[N];
vector<int> g[N];
struct node{
	int ls,rs,val;
}tr[N*170];
struct BCJ{
	int id,rk;
}bcj[N];
int get_id(int x){ return lower_bound(lsh+1,lsh+1+len,x)-lsh; }
int find(int x){ return bcj[x].id==x?x:bcj[x].id=find(bcj[x].id); }
int update(int p,int l,int r,int x)
{
	int k=++id;
	tr[k]=tr[p];
	if(l==r) { tr[k].val++; return k;}
	int mid=(l+r)>>1;
	if(x<=mid) tr[k].ls=update(tr[p].ls,l,mid,x);
	else tr[k].rs=update(tr[p].rs,mid+1,r,x);
	tr[k].val=tr[tr[k].ls].val+tr[tr[k].rs].val;
	return k;
}
int query(int x,int y,int L,int FL,int l,int r,int k)
{
	if(l==r) return l;
	int t=tr[tr[x].ls].val+tr[tr[y].ls].val-tr[tr[L].ls].val-tr[tr[FL].ls].val;
	int mid=(l+r)>>1;
	if(t>=k) return query(tr[x].ls,tr[y].ls,tr[L].ls,tr[FL].ls,l,mid,k);
	else return query(tr[x].rs,tr[y].rs,tr[L].rs,tr[FL].rs,mid+1,r,k-t);
}
void dfs(int u,int las,int root)
{
	dep[u]=dep[las]+1;
	bcj[root].rk++;
	bcj[u].id=root;
	fa[u][0]=las;
	for(int i=1;i<=16;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	rt[u]=update(rt[las],1,len,get_id(a[u]));
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==las) continue;
		dfs(v,u,root);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=16;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=16;i>=0;i--)
		if(fa[x][i]!=fa[y][i]) 
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main()
{
	scanf("%d%d%d%d",&testcase,&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),lsh[i]=a[i];
	sort(lsh+1,lsh+1+n);
	len=unique(lsh+1,lsh+1+n)-lsh-1;
	int x,y,k; char c;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++) bcj[i]={i,1};
	for(int i=1;i<=n;i++)
		if(bcj[i].id==i) dfs(i,0,i);
	while(q--)
	{
		cin>>c;
		scanf("%d%d",&x,&y);
		x^=ans; y^=ans;
		if(c=='Q')
		{
			scanf("%d",&k);
			k^=ans;
			int pos=LCA(x,y);
			ans=lsh[query(rt[x],rt[y],rt[pos],rt[fa[pos][0]],1,len,k)];
			printf("%d\n",ans);
		}
		else
		{
			g[x].push_back(y);
			g[y].push_back(x);
			int rx=find(x),ry=find(y);
			if(bcj[rx].rk<bcj[ry].rk) swap(rx,ry),swap(x,y);
			dfs(x,y,rx);
		}
	}
	return 0;
}