Brief description:
略。)
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)); } } } }