Treap+启发式合并。依旧没什么需要用到脑子的。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define rep(i, l, r) for(int i=l; i<=r; i++)#define clr(x, c) memset(x, c, sizeof(x))#define maxn 100009using namespace std;inline int read(){ int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) x=x*10+ch-'0', ch=getchar(); return x;}int n=read(), m=read();char q[5];int h[maxn], l[maxn], r[maxn], s[maxn], k[maxn], pr[maxn];inline void Init(){srand(2); rep(i, 1, n) s[i]=1, pr[i]=rand();}inline void update(int x){s[x]=s[l[x]]+s[r[x]]+1;}inline void Left(int v){ int u=r[v]; l[h[v]]==v ? l[h[v]]=u : r[h[v]]=u; h[u]=h[v]; r[v]=l[u], h[r[v]]=v; l[u]=v; h[v]=u; update(v), update(u);}inline void Right(int v){ int u=l[v]; l[h[v]]==v ? l[h[v]]=u : r[h[v]]=u; h[u]=h[v]; l[v]=r[u], h[l[v]]=v; r[u]=v, h[v]=u; update(v), update(u);}void Insert(int v, int u){ if (k[v] < k[u]) { if (!l[u]) {l[u]=v, h[v]=u; update(u); return;} Insert(v, l[u]); update(u); if (pr[l[u]] > pr[u]) Right(u); } else { if (!r[u]) {r[u]=v, h[v]=u, update(u); return;} Insert(v, r[u]); update(u); if (pr[r[u]] > pr[u]) Left(u); }}int Top(int v){return h[v]==0 ? v : Top(h[v]);}void Join(int v, int u){ if (v==u) return; if (s[v]>s[u]) swap(v, u); int a=l[v], b=r[v]; h[l[v]]=h[r[v]]=0, l[v]=r[v]=0, s[v]=1; Insert(v, u); if (a) Join(a, u); if (b) Join(b, u);}int Rank(int v, int k){ if (s[v]
           
            k-1) v=l[v]; else k-=s[l[v]]+1, v=r[v]; return v;}int main(){ Init(); rep(i, 1, n) k[i]=read(); rep(i, 1, m) Join(Top(read()), Top(read())); int o=read(); rep(i, 1, o) { int x, y; scanf("%s%d%d", q, &x, &y); if (q[0]=='Q') printf("%d\n", Rank(Top(x), y)); else Join(Top(x), Top(y)); } return 0;}