# 某岛

… : "…アッカリ～ン . .. . " .. .
October 3, 2014

## BZOJ 2733. [HNOI2012]永无乡

### Analysis:


//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

namespace SBT{
const int NN = int(1e5) + 9;
int c[2][NN], sz[NN], ky[NN], tot;
#define lx l[x]
#define rx r[x]
#define l c[d]
#define r c[!d]
#define kx ky[x]
#define sx sz[x]
#define d 0
int new_node(int v = 0){
int x=++tot;lx=rx=0;
sx=1;kx=v;
return x;
}

void upd(int x){
sx=sz[lx]+1+sz[rx];
}
#undef d
void rot(int &x,int d){
int y=rx;rx=l[y];l[y]=x;
upd(x),upd(y),x=y;
}

void fix(int &x,int d){
if (sz[l[lx]] > sz[rx]) rot(x,!d);
else{
if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
else return;
}
d=0,fix(lx,0),fix(rx,1);
fix(x,0),fix(x,1);//upd(x);
}
#define d 0

int mini(int x){
if (lx) return mini(lx);
return ky[x];
}

void iod(int x){
if (!x) return;
iod(lx); printf("%d ", ky[x]); iod(rx);
}

void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
Ins(c[v>kx][x],v);
fix(x,v>=kx);
}
upd(x);
}

void Ins2(int &x, int xx){
if (!x) x = xx;
else{
Ins2(c[ky[xx]>kx][x], xx);
fix(x, ky[xx] >= kx);
}
upd(x);
}

int d_key; void Del(int &x,int v){
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v){
int z=0;while(x){
if(kx<v){
z+=sz[lx]+1;
x=rx;
}
else x=lx;
}
return z;
}

int Select(int x,int k){
if (sz[lx] == k) return x;
return sz[lx]>k?Select(lx,k):Select(rx,k-sz[lx]-1);
}

bool Find(int x,int v){
if (!x) return 0;if (kx==v) return 1;
return Find(c[v>kx][x],v);
}

void Init(){
tot = 0;
}

int Q[N], cz, op;

void Merge(int x, int& y){ // x -> y
cz = 0, op = 1; Q[cz] = x;
while (cz < op){
x = Q[cz++];
if (lx) Q[op++] = lx;
if (rx) Q[op++] = rx;
lx = rx = 0;
Ins2(y, x);
}
}

#undef d
#undef l
#undef r
#undef lx
#undef rx
#undef sx
#undef kx
} //using namespace SBT;

int T[N], P[N], sz[N]; // DSU
int n;

int Find(int x){
return P[x] == x ? x : P[x] = Find(P[x]);
}

void Union(int x, int y){
x = Find(x), y = Find(y); if (x == y) return;
if (sz[T[x]] > sz[T[y]]) swap(x, y);
P[x] = y; SBT::Merge(T[x], T[y]);
}

void Init(){
SBT::Init(); int m; RD(n, m);
REP_1(i, n) T[i] = SBT::new_node(RD()), P[i] = i, sz[i] = 1;
DO(m){
int x, y; RD(x, y);
Union(x, y);
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif

Init(); Rush{
char cmd; int x, y;
RC(cmd); RD(x, y);
if (cmd == 'B'){
Union(x, y);
}
else{
x = Find(x);
if (y > SBT::sz[T[x]]){
OT(-1);
}
else{
--y;
OT(SBT::Select(T[x], y));
}
}
}
}