树上主席树
#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,落泪了