Steven_Meng's Blog

查询第$k$大/小，首先想到主席树，每棵主席树记录当前节点到根节点的路径上面的所有值，每次查询$u,v$，我们使用第$u,v,LCA(u,v),fa[LCA(u,v)]$棵主席树，做一次差分即可。

主要是如何实现连边，最暴力的方式是把$y$所在的联通块的节点全部一个一个连到$x$上面，同时为了实现查询操作，还要更新$LCA$。

考虑优化，注意到只有加边操作，于是可以用启发式合并在$O(\log^2 n)$的时间内实现。

使用并查集，目的是为了获得连通块的大小，以便启发式合并，并查集里面可以路径压缩。

代码：

#include <bits/stdc++.h>
#define MAXN 500005
#define LOG 35
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],b[MAXN],n,m,q;
inline void discrete(){
    for (register int i=1;i<=n;++i) b[i]=a[i];
    sort(b+1,b+1+n);
    for (register int i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    }
}
int rt[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int cnt;
    }tree[MAXN*LOG];
    int tot;
    #define lc(i) tree[i].l
    #define rc(i) tree[i].r
    inline void pushup(int i,int lson,int rson){
        tree[i].cnt=tree[lson].cnt+tree[rson].cnt;
    }
    void Build(int &i,int l,int r){
        i=++tot;
        if (l==r) return ;
        int mid=(l+r)>>1;
        Build(lc(i),l,mid);
        Build(rc(i),mid+1,r);
    }
    void Update(int &i,int pre,int l,int r,int index){
        tree[i=++tot]=tree[pre];
        tree[i].cnt++;
        if (l==r) return void();
        int mid=(l+r)>>1;
        if (index<=mid) Update(lc(i),lc(pre),l,mid,index);
        else Update(rc(i),rc(pre),mid+1,r,index);
    }
    int Query(int rt1,int rt2,int rt3,int rt4,int l,int r,int k){
        if (l==r) return l;
        int mid=(l+r)>>1,cnt=tree[lc(rt1)].cnt+tree[lc(rt2)].cnt-tree[lc(rt3)].cnt-tree[lc(rt4)].cnt;
        if (k<=cnt) return Query(lc(rt1),lc(rt2),lc(rt3),lc(rt4),l,mid,k);
        else return Query(rc(rt1),rc(rt2),rc(rt3),rc(rt4),mid+1,r,k-cnt);
    }
    void Merge(int &rt,int x,int y){
        if (!x||!y) return rt=x+y,void();
        pushup(rt=++tot,x,y);
        Merge(lc(rt),lc(x),lc(y));
        Merge(rc(rt),rc(x),rc(y));
    }
}
using namespace SegmentTree;

void dfs(int,int,int);
inline void AddEdge(int,int);

namespace BCJ{
    int fa[MAXN],sz[MAXN];
    inline void Init(){
        for (register int i=1;i<=n;++i) fa[i]=i;
    }
    int Find(int i){
        return fa[i]==i?i:fa[i]=Find(fa[i]);
    }
    inline void Add(int u,int v){
        AddEdge(u,v);
        AddEdge(v,u);
        int fau=Find(u),fav=Find(v);
        if (sz[fau]<sz[fav]) swap(u,v),swap(fau,fav);
        dfs(v,u,fau);
    }
    inline void Union(int u,int v){
        fa[Find(u)]=Find(v);
    }
}
using namespace BCJ;

vector<int>G[MAXN];
int anc[MAXN][LOG],dep[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int vis[MAXN];
void dfs(int u,int father,int r){
	Update(rt[u],rt[father],1,n,a[u]);
    vis[u]=true,sz[r]++,fa[u]=father;//注意此时的fa为并查集的fa
    anc[u][0]=father;
    dep[u]=dep[father]+1;
    for (register int i=1;i<LOG;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
    for (register int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        if (v==father) continue;
        dfs(v,u,r);
    }
}
inline int LCA(int u,int v){
    if (u==v) return u;
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=LOG-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
    }
    if (u==v) return u;
    for (register int i=LOG-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
    }
    return anc[u][0];
}
inline void Solve(){
    n=read(),m=read(),q=read();
    for (register int i=1;i<=n;++i) a[i]=read();
    discrete();
    for (register int i=1;i<=m;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    Init();
    for (register int i=1;i<=n;++i){
        if (!vis[i]){dfs(i,0,i);fa[i]=i;}
    }
    int lstans=0;
    char ch[3];
    for (register int i=1;i<=q;++i){
        scanf("%s",ch);
        int u=read()^lstans,v=read()^lstans;
        if (ch[0]=='Q'){
            int k=read()^lstans;
            int lca=LCA(u,v);
            printf("%d\n",lstans=b[Query(rt[u],rt[v],rt[lca],rt[anc[lca][0]],1,n,k)]);
        }
        else {
            Add(u,v);
        }
    }
}
int main(){
    int T=read();
    Solve();
}