1. 题目

BZOJ 传送门=￣ω￣=
LUOGU 传送门=￣ω￣=
CODEVS 传送门=￣ω￣=

2. 题解

真是气死人啦！
调了一晚上+一个课间操，都没找出 bug。
重写了 3 次 treap，第一次用指针，第二次用 vector，第三次用静态数组。。。
都错的一模一样！
为什么呢？
中午绝望的我无意中看了看代码中不是 treap 的地方。。。
merge 函数中这句话：

a=findf(a),findf(b);

。。。
你大爷啊！我居然挂在了这里！。。。应该这样写：

a=findf(a),b=findf(b);

。。。。。。。。。。。。。。。。
想起昨天考试，>=写成了>，从 100 分掉到了 10 分。。。。
一种来到非洲的感觉油然而生！
好吧，其实这题很水，就是个并查集维护集合关系，然后启发式合并。
思路具体去看我以前写的用 pb_ds 解决的那个博客吧：
https://www.mina.moe/?p=786

treap 代码：
指针 treap 用了个小技巧，本来节点的构造函数会把节点的 l 和 r 指到 NULL 上。我把它指到了一个叫 def(default) 的节点上，这样可以不用每次都判断是否为 NULL 防止段错误了。
代码 1（指针 treap）：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int v,d,f,s;N*l,*r;N();}*def=new N;
N::N(){v=d=f=s=0,l=r=def;}
struct treap
{
    int size;N*root;
    treap(){size=0,root=def;}
    void update(N*&a){a->s=a->l->s+a->r->s+1;}
    void lrot(N*&a){N*b=a->r;a->r=b->l,b->l=a,b->s=a->s,update(a),a=b;}
    void rrot(N*&a){N*b=a->l;a->l=b->r,b->r=a,b->s=a->s,update(a),a=b;}
    void insert(N*&a,int v,int d)
    {
        if(a==def)
        {
          a=new N;
          a->v=v,a->d=d,a->f=rand(),a->s=1,size++;
          return;
        }
        if(v<a->v){insert(a->l,v,d);if(a->l->f<a->f)rrot(a);}
        else if(v>a->v){insert(a->r,v,d);if(a->r->f<a->f)lrot(a);}
        update(a);
    }
    int kth(N*&a,int k)
    {
        if(a==def)return -1;
        if(k==a->l->s+1)return a->d;
        if(k<=a->l->s)return kth(a->l,k);
        return kth(a->r,k-a->l->s-1);
    }
    void jion(N*&a,treap&b)
    {
        if(a==def)return;
        b.insert(b.root,a->v,a->d),jion(a->l,b),jion(a->r,b);
    }
}t[100005];
int n,m,h[100005],f[100005],q;
int findf(int a){return a==f[a]?a:f[a]=findf(f[a]);}
void merge(int a,int b)
{
    a=findf(a),b=findf(b);
    if(t[h[a]].size>t[h[b]].size)swap(h[a],h[b]);
    t[h[a]].jion(t[h[a]].root,t[h[b]]),f[a]=b;
}
int main()
{
    IN(n),IN(m),srand(n);
    for(int i=1,a;i<=n;i++)f[i]=h[i]=i,IN(a),t[i].insert(t[i].root,a,i);
    for(int i=1,a,b;i<=m;i++)IN(a),IN(b),merge(a,b);
    IN(q);
    for(int i=1,a,b;i<=q;i++)
    {
        char c=getchar();
        while(!isalpha(c))c=getchar();
        IN(a),IN(b);
        if(c=='Q')a=h[findf(a)],printf("%d\n",t[a].kth(t[a].root,b));
        else merge(a,b);
    }
    return 0;
}

静态数组大小开 $nlogn$的大小（稍微开大一点）就行了，因为启发式合并复杂度为 $nlogn$
代码 2（静态数组 treap）：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
static const int ns=3000000;
int n,m,h[100005],f[100005],q,tl[ns],tr[ns],ts[ns],tv[ns],td[ns],tf[ns],tcnt;
struct treap
{
    int size,root;
    treap(){size=root=0;}
    void update(int a){ts[a]=ts[tl[a]]+ts[tr[a]]+1;}
    void lrot(int&a){int b=tr[a];tr[a]=tl[b],tl[b]=a,ts[b]=ts[a],update(a),a=b;}
    void rrot(int&a){int b=tl[a];tl[a]=tr[b],tr[b]=a,ts[b]=ts[a],update(a),a=b;}
    void insert(int&a,int v,int d)
    {
        if(!a){tcnt++,size++,a=tcnt;tf[a]=rand(),tv[a]=v,td[a]=d,ts[a]=1;return;}
        if(v<tv[a]){insert(tl[a],v,d);if(tf[tl[a]]<tf[a])rrot(a);}
        if(v>tv[a]){insert(tr[a],v,d);if(tf[tr[a]]<tf[a])lrot(a);}
        update(a);
    }
    int kth(int&a,int k)
    {
        if(!a)return -1;
        if(ts[tl[a]]+1==k)return td[a];
        if(ts[tl[a]]+1>k)return kth(tl[a],k);
        return kth(tr[a],k-ts[tl[a]]-1);
    }
    void jion(int&a,treap&b)
    {
        if(!a)return;
        b.insert(b.root,tv[a],td[a]),jion(tl[a],b),jion(tr[a],b);
    }
}t[100005];
int findf(int a){return (f[a]==a)?a:f[a]=findf(f[a]);}
void merge(int a,int b)
{
    a=findf(a),b=findf(b);
    if(t[h[a]].size>t[h[b]].size)swap(h[a],h[b]);
    t[h[a]].jion(t[h[a]].root,t[h[b]]),f[a]=b;
}
int main()
{
    IN(n),IN(m),srand(n);
    for(int i=1,a;i<=n;i++)f[i]=h[i]=i,IN(a),t[i].insert(t[i].root,a,i);
    for(int i=1,a,b;i<=m;i++)IN(a),IN(b),merge(a,b);
    IN(q);
    for(int i=1,a,b;i<=q;i++)
    {
        char c=getchar();
        while(!isalpha(c))c=getchar();
        IN(a),IN(b);
        if(c=='Q')a=h[findf(a)],printf("%d\n",t[a].kth(t[a].root,b));
        else merge(a,b);
    }
    return 0;
}