题意：给定一片森林，n个点 每个点有权值 m 条边 q 个操作
操作1： 求x y 路径上的第k大数
操作2： x与y连边
如果没有连边 那就是之前做的裸的树上主席树
连边的话只要用树上启发式合并即可 每次选小的树连到大的树上 （多一个log） 然后再从连接的点更新倍增数组
判断树的大小可以用并查集
经历了无数次RE后发现是lca出了问题
如果我们连边重构 update_LCA 时采用 lg[deep[u]] ，可能存在一种情况：这个点 i 原本的 ans[i][j]，j 最大已经大于了 lg[deep[u]] （即原来深度更深），但是我们更新只是更新到 lg[deep[u]]
所以后来直接改成一个常数就没问题了
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define ull unsigned long long const int N=8e5+5; int T[N],a[N],b[N],lson[N<<5],rson[N<<5],t[N<<5]; int pos,head[N],lg[N],fa[N][20],dep[N],n,m,q,x,y,z,nn,ncnt;int f[N],siz[N]; char s[2]; struct Edge{int to,nex; }edge[N<<1]; void add(int a,int b) { edge[++pos]=(Edge){b,head[a]}; head[a]=pos; } void up(int x,int l,int r,int pre,int &pos) { pos=++ncnt; lson[pos]=lson[pre];rson[pos]=rson[pre];t[pos]=t[pre]+1; if(l==r)return ;int m=(l+r)>>1; if(x<=m)up(x,l,m,lson[pre],lson[pos]); else up(x,m+1,r,rson[pre],rson[pos]); } int qsum(int k,int l,int r,int lca,int falca,int pre,int pos) { if(l==r)return l; int x=t[lson[pos]]+t[lson[pre]]-t[lson[lca]]-t[lson[falca]]; int m=(l+r)>>1; if(k<=x) return qsum(k,l,m,lson[lca],lson[falca],lson[pre],lson[pos]); else return qsum(k-x,m+1,r,rson[lca],rson[falca],rson[pre],rson[pos]); } void dfs(int x,int f) { dep[x]=dep[f]+1; fa[x][0]=f; up(a[x],1,nn,T[f],T[x]); for(int i=1;i<=16;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==f)continue; dfs(v,x); } } int getlca(int x,int y) { if(dep[x]>dep[y])swap(x,y); repp(k,16,0) if(dep[fa[y][k]]>=dep[x]) y=fa[y][k]; if(x==y)return x; for(int k=16;k>=0;--k) if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k]; return fa[x][0]; } int find1(int x) { return x==f[x]?x:find1(f[x]); } void union1(int x,int y) { int a=find1(x),b=find1(y); if(siz[a]>=siz[b]) siz[a]+=siz[b],f[b]=a; else siz[b]+=siz[a],f[a]=b; } int main() { int cas;cin>>cas; scanf("%d%d%d",&n,&m,&q); rep(i,1,n)f[i]=i,siz[i]=1; rep(i,1,n)scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); nn=unique(b+1,b+1+n)-b-1; rep(i,1,n)a[i]=lower_bound(b+1,b+1+nn,a[i])-b; rep(i,1,m) { int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);union1(u,v); } rep(i,1,n) if(f[i]==i)dfs(i,0); int ans=0; while(q--) { RS(s); if(s[0]=='Q') { int k; scanf("%d%d%d",&x,&y,&k);x^=ans;y^=ans;k^=ans; int lca=getlca(x,y); printf("%d ",ans=b[qsum(k,1,nn,T[lca],T[fa[lca][0]],T[x],T[y] )] ); } else { int x,y;scanf("%d%d",&x,&y);x^=ans;y^=ans; add(x,y);add(y,x); int a=find1(x),b=find1(y); if(siz[a]>siz[b])swap(a,b),swap(x,y); f[a]=b;siz[b]+=siz[a]; dfs(x,y); } } return 0; }