传送门 题解：对点到根维护权值线段树，每次连边就进行启发式合并（用size启发），询问就按区间第k大的方式询问，此处不再赘述。
吐槽三点： 1.说好的多组数据其实只有一组，醉了。。。 2.1e9的数据按理说是需要离散化的，但是离散化了反而要RE（可能是个人原因） 3.这个代码片的int为啥是畸形的。。。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=1e5+2; int n,m,q,sb,maxx=0,minx=1e9+7; int a[MAXN];//int b[MAXN]; int fa[MAXN],siz[MAXN]; int root[MAXN],sum[MAXN*260],lc[MAXN*260],rc[MAXN*260],tim=0; int head[MAXN],edge=0,dep[MAXN],anc[MAXN][25]; struct EDGE { int v,nxt; }e[MAXN<<1]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void adde(int u,int v) { e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++; e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++; } int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} void modify(int &rt,int pre,int l,int r,int x) { rt=++tim; sum[rt]=sum[pre]+1; if (l==r) return ; lc[rt]=lc[pre],rc[rt]=rc[pre]; int mid=(l+r)>>1; if (x<=mid) modify(lc[rt],lc[pre],l,mid,x); else modify(rc[rt],rc[pre],mid+1,r,x); } int query(int a,int b,int c,int d,int l,int r,int k) { if (l==r) return l; int temp=sum[lc[a]]+sum[lc[b]]-sum[lc[c]]-sum[lc[d]]; int mid=(l+r)>>1; if (k<=temp) return query(lc[a],lc[b],lc[c],lc[d],l,mid,k); else return query(rc[a],rc[b],rc[c],rc[d],mid+1,r,k-temp); } void dfs(int p,int fat) { dep[p]=dep[fat]+1; anc[p][0]=fat; for (int i=1;i<=18;++i) anc[p][i]=anc[anc[p][i-1]][i-1]; modify(root[p],root[fat],minx,maxx,a[p]); for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v!=fat) dfs(v,p); } } inline int lca(int a,int b) { if (dep[a]<dep[b]) a^=b^=a^=b; for (int i=18;i>=0;--i) if (anc[a][i]&&dep[a]-(1<<i)>=dep[b]) a=anc[a][i]; if (a==b) return a; for (int i=18;i>=0;--i) if (anc[a][i]&&anc[b][i]&&anc[a][i]^anc[b][i]) a=anc[a][i],b=anc[b][i]; return anc[a][0]; } int main() { // freopen("bzoj 3123.in","r",stdin); memset(sum,0,sizeof(sum)); memset(dep,0,sizeof(dep)); memset(head,-1,sizeof(head)); memset(root,0,sizeof(root)); sb=read();//in fact, only one case... n=read(),m=read(),q=read(); for (register int i=1;i<=n;++i) a[i]=read(),maxx=max(maxx,a[i]),minx=min(minx,a[i]),siz[i]=1,fa[i]=i; // sort(b+1,b+n+1); // int nn=unique(b+1,b+n+1)-b-1; // for (register int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+nn+1,a[i])-b; for (register int i=0;i<m;++i) { int u=read(),v=read(); adde(u,v); u=find(u),v=find(v); if (u^v) { if (siz[u]<siz[v]) u^=v^=u^=v; fa[v]=u,siz[u]+=siz[v]; } } for (register int i=1;i<=n;++i) if (!dep[i]) dfs(i,0); int ans=0; for (register int i=0;i<q;++i) { char ss; while (!isalpha(ss=getchar())); if (ss^'L') { int x=read()^ans,y=read()^ans,k=read()^ans; int ff=lca(x,y); ans=query(root[x],root[y],root[ff],root[anc[ff][0]],minx,maxx,k); printf("%d\n",ans); } else { int x=read()^ans,y=read()^ans; int xx=find(x),yy=find(y); if (siz[xx]<siz[yy]) xx^=yy^=xx^=yy,x^=y^=x^=y; fa[yy]=xx,siz[xx]+=siz[yy]; adde(x,y); dfs(y,x); } } return 0; }