文件详细信息

下载本文件

本文件的大小为 3574 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	template<typename T>
	void write(T a){
		static int ch[20],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
const int maxn=80000,maxlog2n=16;
int testcase,n,m,t,log2n,a[maxn+1],b[maxn+1],start[maxn+1];
struct SegmentTree{
	struct Seg{
		int cnt,l,r;
	}T[maxn*(maxlog2n+2)+1];
	int rt[maxn+1];
	void insert(int u1,int u2,int l,int r,int val,int tot){
		while(true){
			T[u2]=T[u1];
			T[u2].cnt++;
			if(l==r)break;
			const int mid=(l+r)>>1;
			if(val<=mid)u1=T[u1].l,T[u2].l=++tot,u2=tot,r=mid;
			else u1=T[u1].r,T[u2].r=++tot,u2=tot,l=mid+1;
		}
	}
	int query(int a,int b,int c,int d,int l,int r,int k){
		while(l<r){
			const int mid=(l+r)>>1,x=T[T[c].l].cnt+T[T[d].l].cnt-T[T[a].l].cnt-T[T[b].l].cnt;
			if(k<=x)a=T[a].l,b=T[b].l,c=T[c].l,d=T[d].l,r=mid;
			else a=T[a].r,b=T[b].r,c=T[c].r,d=T[d].r,l=mid+1,k-=x;
		}
		return l;
	}
}T;
struct Graph{
	int head[maxn+1],total;
	struct Edge{
		int to,next;
	}e[(maxn-1)*2+1];
	inline void add(const int u,const int v){
		e[++total]=Edge{v,head[u]};
		head[u]=total;
	}
	int dep[maxn+1],fa[maxn+1][maxlog2n+1];
	void dfs(const int u,const int from){
		T.insert(T.rt[from],T.rt[u]=start[u],1,n,a[u],start[u]);
		dep[u]=dep[from]+1;
		fa[u][0]=from;
		for(int i=1;i<=log2n;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
		for(int i=head[u];i;i=e[i].next){
			const int v=e[i].to;
			if(v==from)continue;
			dfs(v,u);
		}
	}
	int lca(int x,int y){
		if(dep[x]<dep[y])x^=y^=x^=y;
		while(dep[x]>dep[y])x=fa[x][__builtin_ctz(dep[x]-dep[y])];
		if(x==y)return x;
		for(int i=log2n;i>=0;i--)
			if(fa[x][i]!=fa[y][i])
				x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
}G;
struct DSU{
	int fa[maxn+1],size[maxn+1];
	void init(const int n){
		for(int i=1;i<=n;i++)fa[i]=i;
		for(int i=1;i<=n;i++)size[i]=1;
	}
	int find(const int x){
		return x==fa[x]?x:fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		fa[x]=y;
		size[y]+=size[x];
	}
}dsu;
int main(){
	read(testcase),read(n),read(m),read(t),log2n=31-__builtin_clz(n);
	for(int i=1,pos=1;i<=n;i++)start[i]=pos,pos+=log2n+2;
	for(int i=1;i<=n;i++)read(a[i]);
	memcpy(b+1,a+1,sizeof(int)*n);
	std::sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;
	dsu.init(n);
	for(int i=1,x,y;i<=m;i++){
		read(x),read(y);
		G.add(x,y),G.add(y,x);
		dsu.merge(x,y);
	}
	for(int i=1;i<=n;i++)
		if(dsu.find(i)==i)
			G.dfs(i,0);
	for(int i=1,opt,x,y,k,lca,ans=0;i<=t;i++){
		do opt=gc();
		while(opt!='Q'&&opt!='L');
		read(x),x^=ans,read(y),y^=ans;
		if(opt=='Q'){
			read(k),k^=ans;
			lca=G.lca(x,y);
			write(ans=b[T.query(T.rt[G.fa[lca][0]],T.rt[lca],T.rt[x],T.rt[y],1,n,k)]),pc('\n');
		}else{
			if(dsu.size[dsu.find(x)]<dsu.size[dsu.find(y)])x^=y^=x^=y;
			G.add(x,y),G.add(y,x);
			G.dfs(x,y);
			dsu.merge(x,y);
		}
	}
	return 0;
}