我把 #2 下载下来在 windows 本地是可以跑过的.......

#include<bits/stdc++.h>
using namespace std;
int T,n,m,u,v,k,Fa[5200010][20],Dep[5200010],lastans,rt[5200010],tot;
int b[5200010],bn,a[5200010],siz[5200010],BF[5200010],q;
unordered_map<int,int>to;
vector<int>e[5200010];
struct edge{
	int lef,rig,lefson,rigson;
	int num;
}tr[50200010];
inline void build(int &id,int lef,int rig){
	id=++tot;tr[id].lef=lef;tr[id].rig=rig;
	if(lef==rig)return;
	build(tr[id].lefson,lef,(lef+rig)>>1);
	build(tr[id].rigson,((lef+rig)>>1)+1,rig);
}
inline void modify(int &id,int Lid,int fixid){
	if(tr[Lid].lef>fixid||tr[Lid].rig<fixid)return;
	id=++tot;tr[id]=tr[Lid];
	if(tr[id].lef==tr[id].rig){
		tr[id].num++;return;
	}
	modify(tr[id].lefson,tr[Lid].lefson,fixid);
	modify(tr[id].rigson,tr[Lid].rigson,fixid);
	tr[id].num=tr[tr[id].lefson].num+tr[tr[id].rigson].num;
}
inline void Modify(int id,int Lid,int fixid){
	tr[id].num=tr[Lid].num+1;
	if(tr[id].lef==tr[id].rig)return;
	int mid=(tr[id].lef+tr[id].rig)>>1;
	if(fixid>=mid+1)
		tr[id].lefson=tr[Lid].lefson,Modify(tr[id].rigson,tr[Lid].rigson,fixid);
	else
		tr[id].rigson=tr[Lid].rigson,Modify(tr[id].lefson,tr[Lid].lefson,fixid);
}
inline long long query(int u,int v,int lca,int Flca,int k){
	if(tr[u].lef==tr[u].rig)return tr[u].lef;
	long long now=tr[tr[u].lefson].num+tr[tr[v].lefson].num-
	              tr[tr[lca].lefson].num-tr[tr[Flca].lefson].num;
	if(now>=k)
		return query(tr[u].lefson,tr[v].lefson,tr[lca].lefson,tr[Flca].lefson,k);
	else 
		return query(tr[u].rigson,tr[v].rigson,tr[lca].rigson,tr[Flca].rigson,k-now);
}
inline void dfs1(int id,int fa){
	Dep[id]=Dep[fa]+1;Fa[id][0]=fa;
	for(int i=1;i<=__lg(Dep[id]);i++)Fa[id][i]=Fa[Fa[id][i-1]][i-1];
	modify(rt[id],rt[fa],to[a[id]]);
	for(int v : e[id])if(v!=fa)dfs1(v,id);
}
inline void dfs2(int id,int fa){
	Dep[id]=Dep[fa]+1;memset(Fa[id],0,sizeof Fa[id]);Fa[id][0]=fa;
	for(int i=1;i<=__lg(Dep[id]);i++)Fa[id][i]=Fa[Fa[id][i-1]][i-1];
	Modify(rt[id],rt[fa],to[a[id]]);
	for(int v : e[id])if(v!=fa)dfs2(v,id);
}
inline int findfa(int x){
	if(BF[x]!=x)BF[x]=findfa(BF[x]);
	return BF[x];
}
char op;
int main(){
//	freopen("P3302_2.in","r",stdin);
//	freopen("text.ans","w",stdout);
	cin>>T>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];b[i]=a[i];BF[i]=i;siz[i]=1;
	}Dep[0]=-1;
	stable_sort(b+1,b+n+1);
	bn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)if(!to[a[i]])to[a[i]]=lower_bound(b+1,b+bn+1,a[i])-b;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
		siz[findfa(u)]+=siz[findfa(v)];
		BF[findfa(v)]=findfa(u);
	}
	build(rt[0],1,bn);
	for(int i=1;i<=n;i++)if(findfa(i)==i)dfs1(i,0);
	while(q--){
		cin>>op;
		if(op=='Q'){
			cin>>u>>v>>k;u^=lastans;v^=lastans;k^=lastans;
			long long Fu=u,Fv=v;
			if(Dep[Fu]<Dep[Fv])swap(Fu,Fv);
			for(int i=__lg(Dep[Fu]);i>=0;i--)
				if(Dep[Fa[Fu][i]]>Dep[Fv])Fu=Fa[Fu][i];
			if(Dep[Fu]!=Dep[Fv])Fu=Fa[Fu][0];
			for(int i=__lg(Dep[Fu]);i>=0;i--)
				if(Fa[Fu][i]!=Fa[Fv][i])Fu=Fa[Fu][i],Fv=Fa[Fv][i];
			if(Fu!=Fv)Fu=Fa[Fu][0],Fv=Fa[Fv][0];
			cout<<(lastans=b[query(rt[u],rt[v],rt[Fu],rt[Fa[Fu][0]],k)])<<"\n";
		}
		else{
			cin>>u>>v;
			u^=lastans;v^=lastans;
			e[u].emplace_back(v);
			e[v].emplace_back(u);
			if(siz[findfa(u)]<siz[findfa(v)])swap(u,v);
			siz[findfa(u)]+=siz[findfa(v)];
			BF[findfa(v)]=findfa(u);dfs2(v,u);
		}
	}
}