[bzoj3123][洛谷P3302] [SDOI2013]森林（树上主席树+启发式合并）

传送门

突然发现好像没有那么难……https://blog.****.net/stone41123/article/details/78167288

首先有两个操作，一个查询，一个连接

查询的话，直接在树上建主席树

然后难点在于连接

用启发式合并就可以了（想了半天都没想出来）

每次合并时，我们把小的树接到大的上，然后dfs一遍小的树，更新信息

然后注意数组……别太小也别太大……（被数组大小坑了好几次提交）

 //minamoto
 #include<bits/stdc++.h>
 using namespace std;
 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 char buf[<<],*p1=buf,*p2=buf;
 inline int read(){
     #define num ch-'0'
     char ch;bool flag=;int res;
     while(!isdigit(ch=getc()))
     (ch=='-')&&(flag=true);
     for(res=num;isdigit(ch=getc());res=res*+num);
     (flag)&&(res=-res);
     #undef num
     return res;
 }
 char obuf[<<],*o=obuf;
 void print(int x){
     if(x>) print(x/);
     *o++=x%+;
 }
 const int N=,M=N*;
 int ver[N<<],Next[N<<],head[N];
 int a[N],fa[N],sz[N],b[N];
 int n,m,tot,q,size,ans;
 void add(int u,int v){
     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
 }
 int L[M],R[M],sum[M],rt[N],cnt;
 void update(int last,int &now,int l,int r,int x){
     sum[now=++cnt]=sum[last]+;
     if(l==r) return;
     int mid=(l+r)>>;
     if(x<=mid) R[now]=R[last],update(L[last],L[now],l,mid,x);
     else L[now]=L[last],update(R[last],R[now],mid+,r,x);
 }
 int query(int u,int v,int lca,int lca_fa,int l,int r,int k){
     if(l>=r) return l;
     int x=sum[L[v]]+sum[L[u]]-sum[L[lca]]-sum[L[lca_fa]];
     int mid=(l+r)>>;
     if(x>=k) return query(L[u],L[v],L[lca],L[lca_fa],l,mid,k);
     else return query(R[u],R[v],R[lca],R[lca_fa],mid+,r,k-x);
 }
 inline int hash(int x){
     return lower_bound(b+,b++size,x)-b;
 }
 int ff(int x){
     return fa[x]==x?x:fa[x]=ff(fa[x]);
 }
 int st[N][],d[N],vis[N];
 void dfs(int u,int father,int root){
     st[u][]=father;
     for(int i=;i<=;++i)
     st[u][i]=st[st[u][i-]][i-];
     ++sz[root];
     d[u]=d[father]+;
     fa[u]=root;
     vis[u]=;
     update(rt[father],rt[u],,size,hash(a[u]));
     for(int i=head[u];i;i=Next[i]){
         int v=ver[i];
         if(v==father) continue;
         dfs(v,u,root);
     }
 }
 int LCA(int x,int y){
     if(x==y) return x;
     if(d[x]<d[y]) swap(x,y);
     for(int i=;i>=;--i){
         if(d[st[x][i]]>=d[y]) x=st[x][i];
     }
     if(x==y) return x;
     for(int i=;i>=;--i){
         if(st[x][i]!=st[y][i])
         x=st[x][i],y=st[y][i];
     }
     return st[x][];
 }
 int main(){
     //freopen("testdata.in","r",stdin);
     int t=read();
     n=read(),m=read(),q=read();
     for(int i=;i<=n;++i)
     a[i]=b[i]=read(),fa[i]=i;
     sort(b+,b++n);
     size=unique(b+,b++n)-b-;
     for(int i=;i<=m;++i){
         int u=read(),v=read();
         add(u,v);
     }
     for(int i=;i<=n;++i)
     if(!vis[i]) dfs(i,,i);
     while(q--){
         char ch;int x,y;
         while(!isupper(ch=getc()));
         x=read()^ans,y=read()^ans;
         if(ch=='Q'){
             int k=read()^ans;
             int lca=LCA(x,y);
             ans=b[query(rt[x],rt[y],rt[lca],rt[st[lca][]],,size,k)];
             print(ans),*o++='\n';
         }
         else{
             add(x,y);
             int u=ff(x),v=ff(y);
             if(sz[u]<sz[v]) swap(x,y),swap(u,v);
             dfs(y,x,u);
         }
     }
     fwrite(obuf,o-obuf,,stdout);
     return ;
 }