[bzoj3545]Peaks

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mid (l+r>>1)
 4 #define N 200005
 5 struct ji{
 6     int x,y,z,id;
 7 }e[N*10];
 8 int V,n,m,q,t,f[n],a[n],b[n],r[n],ans[N*5],sz[N*20],ls[N*20],rs[N*20];
 9 bool cmp(ji x,ji y){
10     return (x.z<y.z)||(x.z==y.z)&&(x.id<y.id);
11 }
12 void read(int &n){
13     char c=0;
14     while (!isdigit(C))c=getchar();
15     while (isdigit(C)){
16         n=n*10+(c^48);
17         c=getchar();
18     }
19 }
20 int find(int k){
21     if (k==f[k])return k;
22     return f[k]=find(f[k]);
23 }
24 void update(int k,int l,int r,int X){
25     sz[k]=1;
26     if (l==r)return;
27     if (x<=mid)update(ls[k]=++V,l,mid,X);
28     else update(rs[k]=++V,mid+1,r,X);
29 }
30 int merge(int x,int y){
31     if (x*y==0)return x+y;
32     if (ls[x]+rs[x]==0)sz[x]+=sz[y];
33     else sz[x]=sz[ls[x]=merge(ls[x],ls[y])]+sz[rs[x]=@H_791_31@merge(rs[x],rs[y])];
34     return x;
35 }
36 int query(int k,int X){
37     if (l==r)return l;
38     if (x<=sz[ls[k]])return query(ls[k],X);
39     else return query(rs[k],mid+1,x-sz[ls[k]]);
40 }
41 int main(){
42     read(n);
43     read(m);
44     read(q);
45     for(int i=1;i<=n;i++){
46         read(a[i]);
47         b[f[i]=i]=a[i];
48     }
49     sort(b+1,b+n+1);
50     t=unique(b+1,b+n+1)-b-1;
51     for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+t+1,a[i])-b;
52     for(int i=1;i<=n;i++)update(r[i]=++V,1,a[i]);
53     for(int i=1;i<=m+q;i++){
54         read(e[i].X);
55         read(e[i].y);
56         read(e[i].z);
57         if (i>@H_791_31@m){
58             e[i].id=i-@H_791_31@m;
59             swap(e[i].y,e[i].z);
60         }
61     }
62     m+=q;
63     sort(e+1,e+m+1,cmp);
64     for(int i=1;i<=m;i++){
65         e[i].x=find(e[i].X);
66         if (!e[i].id){
67             e[i].y=find(e[i].y);
68             if (e[i].x==e[i].y)conTinue;
69             f[e[i].x]=e[i].y;
70             r[e[i].y]=@H_791_31@merge(r[e[i].x],r[e[i].y]);
71         }
72         else
73             if (sz[r[e[i].x]]<e[i].y)ans[e[i].id]=-1;
74             else ans[e[i].id]=b[query(r[e[i].x],1,sz[r[e[i].x]]-e[i].y+1)];
75     }
76     for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
77     return 0;
78 }