BZOJ2733：使用并查集维护连通性之后用线段树维护+线段树合并（动态开点）

 1 #include<cstdio>
 2 const int maxn=100005;
 3 int n,m,sz;
 4 int v[maxn],id[maxn],fa[maxn],root[maxn];
 5 int lch[1800000],rch[1800000],sum[1800000];
 6 inline int read()
 7 {
 8     int x=0,f=1;char ch=getchar();
 9     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int find(int x)
14 {
15     return x==fa[x]?x:fa[x]=find(fa[x]);
16 }
17 void insert(int &k,int l,int r,int val)
18 {
19     if(k==0) k=++sz;
20     if(l==r)
21     {
22         sum[k]=1;return;
23     }
24     int mid=(l+r)>>1;
25     if(val<=mid) insert(lch[k],l,mid,val);
26     else insert(rch[k],mid+1,r,val);
27     sum[k]=sum[lch[k]]+sum[rch[k]];
28 }
29 int query(int k,int l,int r,int rank)
30 {
31     if(l==r) return l;
32     int mid=(l+r)>>1;
33     if(sum[lch[k]]>=rank) return query(lch[k],l,mid,rank);
34     else return query(rch[k],mid+1,r,rank-sum[lch[k]]);
35 }
36 int merge(int x,int y)
37 {
38     if(x==0) return y;
39     if(y==0) return x;
40     lch[x]=merge(lch[x],lch[y]);
41     rch[x]=merge(rch[x],rch[y]);
42     sum[x]=sum[lch[x]]+sum[rch[x]];
43     return x;
44 }
45 int main()
46 {
47     n=read();m=read();
48     for(int i=1;i<=n;i++) v[i]=read();
49     for(int i=1;i<=n;i++) fa[i]=i;
50     int x,y;
51     for(int i=1;i<=m;i++)
52     {
53         x=read(),y=read();
54         int p=find(x),q=find(y);
55         fa[p]=q;
56     }
57     for(int i=1;i<=n;i++)
58     {
59         insert(root[find(i)],1,n,v[i]);  //往对应的线段树插点
60         id[v[i]]=i; 
61     }
62     int k=read();
63     char ch[2];
64     while(k--)
65     {
66         scanf("%s",ch);
67         x=read();y=read();
68         if(ch[0]=='Q')
69         {
70             int p=find(x);
71             if(sum[root[p]]<y)
72             {
73                 puts("-1");continue;//查询越界 
74             }
75             int t=query(root[p],1,n,y);  //得到location 
76             printf("%d
",id[t]);
77         }
78         else
79         {
80             int p=find(x),q=find(y);
81             if(p!=q)
82             {
83                 fa[p]=q;
84                 root[q]=merge(root[p],root[q]);
85             }
86         } 
87     }
88     return 0;
89 }