首页 > 代码库 > BZOJ2733: [HNOI2012]永无乡
BZOJ2733: [HNOI2012]永无乡
2733: [HNOI2012]永无乡
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1130 Solved: 583
[Submit][Status]
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
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
2
5
1
2
HINT
Source
题解：
因为支持的操作只有 新建一条边，查询某个连通块内的第k小的值
所以我们考虑用平衡树启发式合并+并查集来完成
刚开始每个节点为一棵平衡树，merge操作只需要找到代表元暴力把小的合并的到大的里面即可
查询操作则直接在代表元的平衡树里面select即可
代码：
1 const maxn=100000+1000; 2 var l,r,s,rnd,v,fa:array[0..maxn] of longint; 3 i,n,m,x,y,xx,yy,rk:longint; 4 ch:char; 5 procedure swap(var x,y:longint); 6 var t:longint; 7 begin 8 t:=x;x:=y;y:=t; 9 end; 10 procedure pushup(k:longint); 11 begin 12 s[k]:=s[l[k]]+s[r[k]]+1; 13 end; 14 procedure rturn(var k:longint); 15 var t:longint; 16 begin 17 t:=l[k];l[k]:=r[t];r[t]:=k;s[t]:=s[k];pushup(k);k:=t; 18 end; 19 procedure lturn(var k:longint); 20 var t:longint; 21 begin 22 t:=r[k];r[k]:=l[t];l[t]:=k;s[t]:=s[k];pushup(k);k:=t; 23 end; 24 procedure ins(var k,x:longint); 25 begin 26 if k=0 then 27 begin 28 k:=x;s[k]:=1;l[k]:=0;r[k]:=0; 29 rnd[k]:=random(maxlongint);exit; 30 end; 31 inc(s[k]); 32 if v[x]<v[k] then begin ins(l[k],x);if rnd[l[k]]<rnd[k] then rturn(k);end 33 else begin ins(r[k],x);if rnd[r[k]]<rnd[k] then lturn(k);end; 34 end; 35 procedure print(x:longint); 36 begin 37 if x=0 then exit; 38 print(l[x]); 39 write(x,‘ ‘,v[x],‘!‘); 40 print(r[x]); 41 end; 42 function select(k,rk:longint):longint; 43 begin 44 if s[l[k]]+1=rk then exit(k) 45 else if s[l[k]]>=rk then exit(select(l[k],rk)) 46 else exit(select(r[k],rk-1-s[l[k]])); 47 end; 48 function find(x:longint):longint; 49 begin 50 if fa[x]<>x then fa[x]:=find(fa[x]); 51 exit(fa[x]); 52 end; 53 procedure merge(x,y:longint); 54 begin 55 if x=0 then exit; 56 merge(l[x],y);merge(r[x],y);ins(y,x); 57 end; 58 procedure solvemerge; 59 begin 60 readln(x,y); 61 xx:=find(x);yy:=find(y); 62 if s[xx]>s[yy] then swap(xx,yy); 63 fa[xx]:=yy; 64 merge(xx,yy); 65 end; 66 procedure solveask; 67 begin 68 readln(x,rk); 69 xx:=find(x); 70 if rk>s[xx] then writeln(‘-1‘) else writeln(select(xx,rk)); 71 end; 72 procedure init; 73 begin 74 readln(n,m); 75 for i:=1 to n do 76 begin 77 read(v[i]); 78 fa[i]:=i;s[i]:=1;l[i]:=0;r[i]:=0; 79 end; 80 for i:=1 to m do solvemerge; 81 end; 82 procedure main; 83 begin 84 readln(m); 85 for i:=1 to m do 86 begin 87 read(ch); 88 case ch of 89 ‘B‘:solvemerge; 90 ‘Q‘:solveask; 91 end; 92 end; 93 end; 94 begin 95 assign(input,‘input.txt‘);assign(output,‘output.txt‘); 96 reset(input);rewrite(output); 97 init; 98 main; 99 close(input);close(output);100 end.