前置技能：Count on a tree
然后带上一个启发式合并
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, orz, uu, vv, ww, a[80005], b[80005], rnk[80005], rem, cnt, tt[15];
int hea[80005], fa[80005], siz[80005], gra[80005][19], qaq, lst;
int rot[80005], lson[9000005], rson[9000005], sum[9000005], dep[80005];
bool vis[80005];
char ss[15];
struct Edge{
int too, nxt;
}edge[320005];
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
int insert(int pre, int l, int r, int x){
int rt=++qaq;
int mid=(l+r)>>1;
lson[rt] = lson[pre]; rson[rt] = rson[pre]; sum[rt] = sum[pre] + 1;
if(l==r) return rt;
if(x<=mid) lson[rt] = insert(lson[pre], l, mid, x);
if(mid<x) rson[rt] = insert(rson[pre], mid+1, r, x);
return rt;
}
void dfs(int o, int f, int r){
fa[o] = f;
siz[r]++;
dep[o] = dep[f] + 1;
vis[o] = true;
gra[o][0] = f;
for(int i=1; i<=16; i++)
gra[o][i] = gra[gra[o][i-1]][i-1];
rot[o] = insert(rot[f], 1, rem, rnk[o]);
for(int i=hea[o]; i; i=edge[i].nxt){
int t=edge[i].too;
if(t!=f) dfs(t, o, r);
}
}
int build(int l, int r){
int rt=++qaq;
int mid=(l+r)>>1;
if(l==r) return rt;
if(l<=mid) lson[rt] = build(l, mid);
if(mid<r) rson[rt] = build(mid+1, r);
return rt;
}
int getLca(int uu, int vv){
if(dep[uu]<dep[vv]) swap(uu, vv);
for(int i=16; i>=0; i--)
if(dep[gra[uu][i]]>=dep[vv])
uu = gra[uu][i];
if(uu==vv) return uu;
for(int i=16; i>=0; i--)
if(gra[uu][i]!=gra[vv][i]){
uu = gra[uu][i];
vv = gra[vv][i];
}
return gra[uu][0];
}
int query(int l, int r, int k){
int tmp=0;
tmp -= sum[lson[tt[1]]] + sum[lson[tt[2]]];
tmp += sum[lson[tt[3]]] + sum[lson[tt[4]]];
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=tmp){
for(int i=1; i<=4; i++)
tt[i] = lson[tt[i]];
return query(l, mid, k);
}
else{
for(int i=1; i<=4; i++)
tt[i] = rson[tt[i]];
return query(mid+1, r, k-tmp);
}
}
int myfind(int x){
return x==fa[x]?x:fa[x]=myfind(fa[x]);
}
int main(){
cin>>n;
cin>>n>>m>>orz;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
fa[i] = i;
}
sort(b+1, b+1+n);
rem = unique(b+1, b+1+n) - (b + 1);
for(int i=1; i<=n; i++){
int tmp=lower_bound(b+1, b+1+rem, a[i])-b;
rnk[i] = tmp;
}
for(int i=1; i<=m; i++){
scanf("%d %d", &uu, &vv);
add_edge(uu, vv);
add_edge(vv, uu);
}
rot[0] = build(1, rem);
for(int i=1; i<=n; i++)
if(!vis[i])
dfs(i, 0, i), fa[i]=i;
while(orz--){
scanf("%s", ss);
if(ss[0]=='Q'){
scanf("%d %d %d", &uu, &vv, &ww);
uu ^= lst; vv ^= lst; ww ^= lst;
int lca=getLca(uu, vv);
tt[1] = rot[lca]; tt[2] = rot[gra[lca][0]];
tt[3] = rot[uu]; tt[4] = rot[vv];
lst = b[query(1, rem, ww)];
printf("%d
", lst);
}
else{
scanf("%d %d", &uu, &vv);
uu ^= lst; vv ^= lst;
int r1=myfind(uu);
int r2=myfind(vv);
if(siz[r1]<siz[r2]) swap(uu, vv), swap(r1, r2);
add_edge(uu, vv);
add_edge(vv, uu);
dfs(vv, uu, r1);
}
}
return 0;
}