rt

我大概翻了一下讨论区，目前可以确定这些错误我应该是没有的：

• 合并时忘加新边

• 更新倍增祖先时没更新彻底

• dfs时没有从 y 点开始搜而是选择从 y 点的并查集祖先开始搜

试过数组开大到 $\text{128N}$，但仍然寄了QAQ

#include<bits/stdc++.h>
#define N 80004
#define K 17
#define T (K+2)*N
#define L lc[no]
#define R rc[no]
using namespace std;
int n,m,t,cnt,fir[N],bh,val[N],lsh[N],len,dep[N],fa[N][K],sz[N],ans,f[N],ro[N];
unordered_map<int,int>op;
struct E{ int nex,to;}e[N<<1];
struct tree{
    int lc[T],rc[T],num[T];
    inline void ins(int &no,int pre,int l,int r,int pl){
        if(l>pl||r<pl) return ;
        no=++bh,lc[no]=lc[pre],rc[no]=rc[pre],num[no]=num[pre];
        if(l==r){ ++num[no]; return ;}
        int mi=l+r>>1;
        ins(L,L,l,mi,pl),ins(R,R,mi+1,r,pl);
        num[no]=num[L]+num[R];
    }
    inline int qur(int q1,int w2,int e3,int t4,int l,int r,int k){
        if(l==r) return lsh[l];
        int mi=l+r>>1,l1=lc[q1],l2=lc[w2],l3=lc[e3],l4=lc[t4],r1=rc[q1],r2=rc[w2],r3=rc[e3],r4=rc[t4],ln=num[l1]+num[l4]-num[l2]-num[l3];
        if(ln>=k)
            return qur(l1,l2,l3,l4,l,mi,k);
        return qur(r1,r2,r3,r4,mi+1,r,k-ln);
    }
    inline void add(int no,int pre,int l,int r,int pl){
        if(l>pl||r<pl) return ;
        lc[no]=lc[pre],rc[no]=rc[pre],num[no]=num[pre];
        if(l==r){ ++num[no]; return ;}
        int mi=l+r>>1;
        add(L,L,l,mi,pl),add(R,R,mi+1,r,pl);
        num[no]=num[L]+num[R];
    }
}tr;
void add(int,int),join(int,int),dfs(int),com(int,int),reb(int,int);
int find(int),lca(int,int);
signed main(){
    int ml; scanf("%d%d%d%d",&ml,&n,&m,&t);
    for(int i=1;i<=n;++i)
        scanf("%d",&val[i]),lsh[++len]=val[i],f[i]=i;
    sort(lsh+1,lsh+1+n),len=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=len;++i)
        op[lsh[i]]=i;
    for(int i=1,a,b;i<=m;++i)
        scanf("%d%d",&a,&b),add(a,b);
    for(int i=1;i<=n;++i)
        if(!dep[i])
            dep[i]=1,tr.ins(ro[i],0,1,len,op[val[i]]),dfs(i);
    while(t--){
        char s[2]; int x,y,k,lc; scanf("%s%d%d",s,&x,&y),x^=ans,y^=ans;
        if(s[0]=='Q'){
            scanf("%d",&k),k^=ans,lc=lca(x,y);
            printf("%d\n",ans=tr.qur(ro[x],ro[lc],ro[fa[lc][0]],ro[y],1,len,k));
        }
        else com(x,y);
    }
    return 0;
}
void add(int a,int b){ e[++cnt].nex=fir[a],e[cnt].to=b,fir[a]=cnt,e[++cnt].nex=fir[b],e[cnt].to=a,fir[b]=cnt;}
int find(int a){ return f[a]==a?a:f[a]=find(f[a]);}
void join(int a,int b){
    int aa=find(a),bb=find(b);
    if(dep[aa]>dep[bb]) swap(aa,bb);
    if(aa!=bb) f[bb]=aa;
}
void dfs(int no){
    ++sz[no];
    for(int i=1;i<K;++i)
        fa[no][i]=fa[fa[no][i-1]][i-1];
    for(int i=fir[no];i;i=e[i].nex){
        int v=e[i].to; if(dep[v]) continue;
        dep[v]=dep[no]+1,join(no,v),fa[v][0]=no;
        tr.ins(ro[v],ro[no],1,len,op[val[v]]);
        dfs(v),sz[no]+=sz[v];
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=K-1;i>=0;--i)
        if(dep[fa[a][i]]>=dep[b])
            a=fa[a][i];
    if(a==b) return a;
    for(int i=K-1;i>=0;--i)
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
void com(int a,int b){
    int aa=find(a),bb=find(b);
    if(sz[aa]<sz[bb])
        swap(aa,bb);
    f[bb]=aa,sz[aa]+=bb,dep[b]=dep[a]+1;
    tr.add(ro[b],ro[a],1,len,op[val[b]]);
    reb(b,a),add(a,b);
}
void reb(int no,int f){
    fa[no][0]=f;
    for(int i=1;i<K;++i)
        fa[no][i]=fa[fa[no][i-1]][i-1];
    for(int i=fir[no];i;i=e[i].nex){
        int v=e[i].to; if(v==f) continue;
        dep[v]=dep[no]+1;
        tr.add(ro[v],ro[no],1,len,op[val[v]]);
        reb(v,no);
    }
}