$R_E 70$ 求助

#include<bits/stdc++.h>
using namespace std;
const int mxn=8e4+5,mxm=3e7+5;
struct ed {
    int to,nxt;
}t[mxn<<1];
int n,m,q,s,ans,tot,cnt;
int a[mxn],b[mxn],dep[mxn],anc[mxn],sum[mxm],hd[mxn],sz[mxn],ls[mxm],rs[mxm],rt[mxm],f[mxn][20];

inline void add(int u,int v) {
    t[++cnt]=(ed){v,hd[u]},hd[u]=cnt;
}

int find(int x) {
    return anc[x]==x?x:anc[x]=find(anc[x]);
}

void update(int,int&,int,int,int);

void dfs(int u,int fa)
{
    f[u][0]=fa; dep[u]=dep[fa]+1;
    update(rt[fa],rt[u],1,s,b[u]);
    for(int i=1;i<=19;++i) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        dfs(v,u);
    }
}

void update(int las,int& p,int l,int r,int val)
{
    p=++tot; sum[p]=sum[las]+1;
    if(l==r) return ; int mid=(l+r)>>1;
    if(val<=mid) update(ls[las],ls[p],l,mid,val),rs[p]=rs[las];
    else update(rs[las],rs[p],mid+1,r,val),ls[p]=ls[las];
}

int query(int las1,int las2,int p1,int p2,int l,int r,int k)
{
    if(l==r) return a[l]; int mid=(l+r)>>1;
    int tp=sum[ls[p1]]+sum[ls[p2]]-sum[ls[las1]]-sum[ls[las2]];
    if(k<=tp) return query(ls[las1],ls[las2],ls[p1],ls[p2],l,mid,k);
    else return query(rs[las1],rs[las2],rs[p1],rs[p2],mid+1,r,k-tp);
}

void build(int &p,int l,int r,int val)
{
    p=++tot; sum[p]=1;
    if(l==r) return ; int mid=(l+r)>>1;
    if(val<=mid) build(ls[p],l,mid,val);
    else build(rs[p],mid+1,r,val);
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;--i) 
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;--i)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}

void link(int u,int v)
{
    u^=ans,v^=ans;
    add(u,v),add(v,u);
    int x=find(u),y=find(v);
    if(sz[x]>sz[y]) swap(x,y),swap(u,v);
    anc[u]=v; sz[y]+=sz[x];
    dfs(u,v); 
}

void solve(int u,int v,int k)
{
    u^=ans,v^=ans,k^=ans;
    int lca=LCA(u,v);
    ans=query(rt[lca],rt[f[lca][0]],rt[u],rt[v],1,s,k);
    printf("%d\n",ans);
}

int main()
{
    int u,v,w; char opt[4];
    scanf("%d%d%d%d",&u,&n,&m,&q);
    for(int i=1;i<=n;++i) sz[i]=1,anc[i]=i;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    sort(a+1,a+n+1); s=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;++i) 
        b[i]=lower_bound(a+1,a+n+1,b[i])-a,build(rt[i],1,s,b[i]);
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    
    for(int i=1;i<=q;++i) {
        scanf("%s",opt);
        if(opt[0]=='Q') 
            scanf("%d%d%d",&u,&v,&w),solve(u,v,w);
        else 
            scanf("%d%d",&u,&v),link(u,v);
    }
    
    return 0;
}