对于操作1，显然可以使用主席树维护，然后对于一条链(x,y)，假设lca为f，根为rt，则(rt,x)+(rt,y)-(rt,f)-(rt,fa[f])即为所求的链，在主席树上直接查询即可，查询方式类似于treap/splay对size的询问。
对于操作2，可以用LCT，当然也能启发式合并，每次连边时，强行把sz小的塞入sz大的即可。
#include<bits/stdc++.h> using namespace std; const int N=80100; int n,m,p,a[N],b[N],rt[N],sz[N],fa[N],dep[N],f[N][20]; vector<int>G[N]; namespace tree{ struct seg{int lc,rc,s;}tr[N*400]; int sz; void update(int k,int l,int r,int&rt,int prt) { tr[rt=++sz]=tr[prt],tr[rt].s++; if(l==r)return; int mid=l+r>>1; if(k<=mid)update(k,l,mid,tr[rt].lc,tr[prt].lc); else update(k,mid+1,r,tr[rt].rc,tr[prt].rc); } int query(int u,int v,int pu,int pv,int k,int l,int r) { if(l==r)return l; int mid=l+r>>1,sum=tr[tr[u].lc].s+tr[tr[v].lc].s-tr[tr[pu].lc].s-tr[tr[pv].lc].s; if(k<=sum)return query(tr[u].lc,tr[v].lc,tr[pu].lc,tr[pv].lc,k,l,mid); return query(tr[u].rc,tr[v].rc,tr[pu].rc,tr[pv].rc,k-sum,mid+1,r); } } int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void dfs(int u,int Fa,int anc) { f[u][0]=Fa; for(int i=1;i<=19;i++)f[u][i]=f[f[u][i-1]][i-1]; sz[anc]++,dep[u]=dep[Fa]+1,fa[u]=Fa; int x=lower_bound(b+1,b+p+1,a[u])-b; tree::update(x,1,p,rt[u],rt[Fa]); for(int i=0;i<G[u].size();i++)if(G[u][i]!=Fa)dfs(G[u][i],u,anc); } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y]; for(int i=0;(1<<i)<=t;i++)if(t&(1<<i))x=f[x][i]; if(x==y)return x; for(int i=19;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } int main() { int Q;scanf("%*d%d%d%d",&n,&m,&Q); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i],fa[i]=i; for(int i=1,x,y;i<=m ;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); sort(b+1,b+n+1); p=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)if(!dep[i])dfs(i,0,i),fa[i]=i; char op; int x,y,z,ans=0; while(Q--) { scanf(" %c%d%d",&op,&x,&y),x^=ans,y^=ans; if(op=='Q') { scanf("%d",&z),z^=ans; int Fa=lca(x,y); printf("%d ",ans=b[tree::query(rt[x],rt[y],rt[Fa],rt[f[Fa][0]],z,1,p)]); } else{ G[x].push_back(y),G[y].push_back(x); int fx=find(x),fy=find(y); if(sz[fx]<sz[fy])swap(x,y),swap(fx,fy); dfs(y,x,fx); } } }