好久没写treap，稍微练练
treap的启发式合并
1 const key=2000007; 2 var son:array[0..100010,1..2] of longint; 3 root,a,b,fa,count,f:array[0..100010] of longint; 4 j,n,m,k,x,y,i:longint; 5 ch:char; 6 7 function getf(x:longint):longint; 8 begin 9 if f[x]<>x then f[x]:=getf(f[x]); 10 exit(f[x]); 11 end; 12 13 procedure update(x:longint); 14 begin 15 count[x]:=count[son[x,1]]+count[son[x,2]]+1; 16 end; 17 18 procedure rotate(x,w:longint); 19 var y:longint; 20 begin 21 y:=fa[x]; 22 if fa[y]<>0 then 23 begin 24 if son[fa[y],1]=y then son[fa[y],1]:=x 25 else son[fa[y],2]:=x; 26 end; 27 fa[x]:=fa[y]; 28 son[y,3-w]:=son[x,w]; 29 if son[x,w]<>0 then fa[son[x,w]]:=y; 30 son[x,w]:=y; 31 fa[y]:=x; 32 update(y); 33 update(x); 34 end; 35 36 procedure up(i,x:longint); 37 var j:longint; 38 begin 39 j:=fa[i]; 40 while j<>0 do 41 begin 42 if b[i]<b[j] then 43 begin 44 if son[j,1]=i then rotate(i,2) 45 else rotate(i,1); 46 end 47 else break; 48 j:=fa[i]; 49 end; 50 if fa[i]=0 then root[x]:=i; 51 end; 52 53 procedure insert(x,y:longint); 54 var p:longint; 55 begin 56 b[x]:=trunc(random*key)+1; 57 count[x]:=1; 58 son[x,1]:=0; 59 son[x,2]:=0; 60 p:=root[y]; 61 repeat 62 inc(count[p]); 63 if a[p]>=a[x] then 64 begin 65 if son[p,1]=0 then break; 66 p:=son[p,1]; 67 end 68 else begin 69 if son[p,2]=0 then break; 70 p:=son[p,2]; 71 end; 72 until false; 73 fa[x]:=p; 74 if a[p]>=a[x] then son[p,1]:=x else son[p,2]:=x; 75 up(x,y); 76 end; 77 78 procedure succ(x,y:longint); 79 begin 80 if son[x,1]<>0 then succ(son[x,1],y); 81 if son[x,2]<>0 then succ(son[x,2],y); 82 insert(x,y); 83 end; 84 85 procedure union(x,y:longint); 86 var k1,k2:longint; 87 begin 88 k1:=getf(x); 89 k2:=getf(y); 90 if k1<>k2 then 91 begin 92 if count[root[k1]]>count[root[k2]] then 93 begin 94 f[k2]:=k1; 95 succ(root[k2],k1); 96 end 97 else begin 98 f[k1]:=k2; 99 succ(root[k1],k2); 100 end; 101 end; 102 end; 103 104 function find(k,x:longint):longint; 105 var p:longint; 106 begin 107 p:=root[x]; 108 while p<>0 do 109 begin 110 if count[son[p,1]]+1=k then exit(p); 111 if count[son[p,1]]+1>k then p:=son[p,1] 112 else begin 113 k:=k-count[son[p,1]]-1; 114 p:=son[p,2]; 115 end; 116 end; 117 exit(-1); 118 end; 119 120 begin 121 randomize; 122 readln(n,k); 123 for i:=1 to n do 124 begin 125 read(a[i]); 126 b[i]:=trunc(random*key)+1; 127 f[i]:=i; 128 root[i]:=i; 129 end; 130 for i:=1 to k do 131 begin 132 readln(x,y); 133 union(x,y); 134 end; 135 readln(m); 136 for i:=1 to m do 137 begin 138 readln(ch,x,y); 139 if ch='Q' then 140 begin 141 x:=getf(x); 142 writeln(find(y,x)); 143 end 144 else union(x,y); 145 end; 146 end.