Description
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000
对于 100%的数据 n≤100000,m≤n，q≤300000
Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
Sample Input
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
Sample Output
-1
2
5
1
2
平衡树启发式合并
每次合并都把小的拆开，放到大的里面（听说数据很水，随机的，不旋转就可以过，写了一个，然后就pascal的rank1了）
还是正常一点写一个splay吧(不过常数有点大，所以是深度超过32才splay)
1 const 2 maxn=100010; 3 dep=32; 4 type 5 node=record 6 son:array[0..1]of longint; 7 size,data,fa:longint; 8 end; 9 var 10 tree:array[0..maxn]of node; 11 f,root:array[0..maxn]of longint; 12 n,m,q:longint; 13 14 function find(x:longint):longint; 15 begin 16 if f[x]=x then exit(x); 17 f[x]:=find(f[x]); 18 exit(f[x]); 19 end; 20 21 procedure rotate(x,w:longint;var root:longint); 22 var 23 y:longint; 24 begin 25 y:=tree[x].fa; 26 tree[y].son[w]:=tree[x].son[w xor 1]; 27 if tree[x].son[w xor 1]<>0 then tree[tree[x].son[w xor 1]].fa:=y; 28 tree[x].son[w xor 1]:=y; 29 if y=root then root:=x 30 else 31 if tree[tree[y].fa].son[0]=y then tree[tree[y].fa].son[0]:=x 32 else tree[tree[y].fa].son[1]:=x; 33 tree[x].fa:=tree[y].fa; 34 tree[y].fa:=x; 35 tree[y].size:=tree[tree[y].son[0]].size+tree[tree[y].son[1]].size+1; 36 end; 37 38 procedure splay(x:longint;var root:longint); 39 var 40 y:longint; 41 begin 42 while root<>x do 43 begin 44 y:=tree[x].fa; 45 if y=root then 46 if tree[y].son[0]=x then rotate(x,0,root) 47 else rotate(x,1,root) 48 else 49 if tree[tree[y].fa].son[0]=y then 50 if tree[y].son[0]=x then 51 begin 52 rotate(y,0,root); 53 rotate(x,0,root); 54 end 55 else 56 begin 57 rotate(x,1,root); 58 rotate(x,0,root); 59 end 60 else 61 if tree[y].son[0]=x then 62 begin 63 rotate(x,0,root); 64 rotate(x,1,root); 65 end 66 else 67 begin 68 rotate(y,1,root); 69 rotate(x,1,root); 70 end; 71 end; 72 tree[x].size:=tree[tree[x].son[0]].size+tree[tree[x].son[1]].size+1; 73 end; 74 75 procedure insert(x:longint;var root:longint); 76 var 77 now,step:longint; 78 begin 79 now:=root; 80 step:=0; 81 while true do 82 begin 83 inc(step); 84 inc(tree[now].size); 85 if tree[x].data<tree[now].data then 86 if tree[now].son[0]=0 then break 87 else now:=tree[now].son[0] 88 else 89 if tree[now].son[1]=0 then break 90 else now:=tree[now].son[1]; 91 end; 92 if tree[x].data<tree[now].data then tree[now].son[0]:=x 93 else tree[now].son[1]:=x; 94 tree[x].size:=1; 95 tree[x].son[0]:=0; 96 tree[x].son[1]:=0; 97 tree[x].fa:=now; 98 if step>dep then splay(x,root); 99 end; 100 101 procedure dfs(x:longint;var root:longint); 102 begin 103 with tree[x] do 104 begin 105 if son[0]<>0 then dfs(son[0],root); 106 if son[1]<>0 then dfs(son[1],root); 107 insert(x,root); 108 end; 109 end; 110 111 procedure union(x,y:longint); 112 var 113 u,v:longint; 114 begin 115 u:=find(x); 116 v:=find(y); 117 if u=v then exit; 118 if tree[root[u]].size<tree[root[v]].size then 119 begin 120 dfs(root[u],root[v]); 121 f[u]:=v; 122 end 123 else 124 begin 125 dfs(root[v],root[u]); 126 f[v]:=u; 127 end; 128 end; 129 130 procedure init; 131 var 132 i,x,y:longint; 133 begin 134 read(n,m); 135 for i:=1 to n do 136 begin 137 f[i]:=i; 138 root[i]:=i; 139 tree[i].size:=1; 140 end; 141 for i:=1 to n do 142 read(tree[i].data); 143 for i:=1 to m do 144 begin 145 read(x,y); 146 union(x,y); 147 end; 148 end; 149 150 function ans(k:longint;var root:longint):longint; 151 var 152 now,step:longint; 153 begin 154 now:=root; 155 step:=0; 156 if k>tree[now].size then exit(-1); 157 while true do 158 begin 159 inc(step); 160 if k=tree[tree[now].son[0]].size+1 then 161 begin 162 if step>dep then splay(now,root); 163 exit(now); 164 end; 165 if k<=tree[tree[now].son[0]].size then now:=tree[now].son[0] 166 else 167 begin 168 dec(k,tree[tree[now].son[0]].size+1); 169 now:=tree[now].son[1]; 170 end; 171 end; 172 end; 173 174 procedure work; 175 var 176 i,x,y:longint; 177 c:char; 178 begin 179 readln(q); 180 for i:=1 to q do 181 begin 182 readln(c,x,y); 183 if c='Q' then 184 begin 185 if (x>n) or (x<1) then writeln(-1) 186 else writeln(ans(y,root[find(x)])); 187 end 188 else union(x,y); 189 end; 190 end; 191 192 begin 193 init; 194 work; 195 end.