C56 可持久化线段树+LCA+按秩合并 P3302 [SDOI2013] 森林

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int read(){ //快读
  int s=0; char c=getchar();
  while(c>'9'||c<'0') c=getchar();
  while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
  return s;    
}
const int N=80005;
#define mid ((l+r)>>1)
int h[N*2],to[N*4],ne[N*4],idx; //邻接表
void add(int x,int y){
  to[++idx]=y;ne[idx]=h[x];h[x]=idx;
}
int n,m,T,last;
int a[N],b[N],bn;    //b:离散化
int rt[N],siz[N];    //集合的根,大小
int f[N][25],dep[N]; //LCA数组
int root[N],tot;     //线段树的根,开点个数
int ls[N*150],rs[N*150],sum[N*150]; //可持久线段树
// sum:区间数的出现次数的前缀和
void change(int &u,int v,int l,int r,int p){ //点修
  u=++tot; //动态开点
  ls[u]=ls[v]; rs[u]=rs[v]; sum[u]=sum[v]+1;
  if(l==r) return;  //双指针同步搜索
  if(p<=mid) change(ls[u],ls[v],l,mid,p);
  else       change(rs[u],rs[v],mid+1,r,p);
}
void dfs(int u,int fa,int p){ //预处理
  rt[u]=p; siz[p]++; //记录集合的根与大小
  change(root[u],root[fa],1,bn,a[u]); //建持久化线段树
  dep[u]=dep[fa]+1; f[u][0]=fa;
  for(int i=1;i<=18;i++)
    f[u][i]=f[f[u][i-1]][i-1];
  for(int i=h[u];i;i=ne[i])
    if(to[i]!=fa) dfs(to[i],u,p);
}
int LCA(int u,int v){ //返回LCA
  if(dep[u]<dep[v]) swap(u,v);
  for(int i=18; i>=0; i--)
    if(dep[f[u][i]]>=dep[v]) u=f[u][i];
  if(u==v) return u;
  for(int i=18; i>=0; i--)
    if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
  return f[u][0];
}
int query(int u,int v,int x,int y,int l,int r,int k){ //点查
  if(l==r) return b[l];            //四指针同步搜索
  int s=sum[ls[u]]+sum[ls[v]]-sum[ls[x]]-sum[ls[y]];
  if(k<=s)return query(ls[u],ls[v],ls[x],ls[y],l,mid,k);
  else return    query(rs[u],rs[v],rs[x],rs[y],mid+1,r,k-s);
}
int main(){
  read();n=read();m=read();T=read(); int x,y,k;
  for(int i=1;i<=n;i++)
    b[i]=a[i]=read(),rt[i]=i;    //每个点的根是自己
  sort(b+1,b+1+n);
  bn=unique(b+1,b+1+n)-(b+1); //去重
  for(int i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+1+bn,a[i])-b; //离散值
  for(int i=1;i<=m;i++)
    x=read(),y=read(),add(x,y),add(y,x); //连边
  for(int i=1;i<=n;i++)
    if(rt[i]==i) dfs(i,0,i); //预处理
  for(int i=1;i<=T;i++){
    char s[2]; scanf("%s",s); x=read()^last; y=read()^last;
    if(s[0]=='Q'){
      k=read()^last; int lca=LCA(x,y),fa=f[lca][0];
      last=query(root[x],root[y],root[lca],root[fa],1,bn,k);
      printf("%d\n",last);
    }
    else{
      add(x,y); add(y,x); //连边，按秩合并
      siz[rt[x]]>siz[rt[y]] ? dfs(y,x,rt[x]):dfs(x,y,rt[y]);
    }
  }
}