首页 > > 程序设计 > C/C++ >

bzoj2733 [ HNOI2012 ] -- 并查集+线段树合并

2018-06-17 23:14:17来源：未知阅读 ()

用并查集记录每个联通块的根节点，每个联通块建一棵线段树，合并时合并线段树就可以了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define N 100010
 6 struct node{
 7     int l,r,x;
 8 }c[N*20];
 9 int i,j,k,n,m,l,r,a[N],x,y,Rt[N],Num,b[N],f[N],f1,f2;
10 char s[2];
11 inline int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
12 inline void Update(int& Node,int l,int r,int x){
13     if(!Node)Node=++Num;
14     if(l==r){c[Node].x++;return;} 
15     int Mid=l+r>>1;
16     if(Mid<x)Update(c[Node].r,Mid+1,r,x);else Update(c[Node].l,l,Mid,x);
17     c[Node].x=c[c[Node].l].x+c[c[Node].r].x; 
18 }
19 inline int Merge(int x,int y){
20     if(!y)return x;
21     if(!x)return y;
22     c[x].l=Merge(c[x].l,c[y].l);
23     c[x].r=Merge(c[x].r,c[y].r);
24     c[x].x=c[c[x].l].x+c[c[x].r].x;
25     return x;
26 }
27 inline int Query(int Node,int l,int r,int R){
28     if(l>R||!Node)return 0;
29     if(r<=R)return c[Node].x;
30     int Mid=l+r>>1;
31     return Query(c[Node].l,l,Mid,R)+Query(c[Node].r,Mid+1,r,R);
32 }
33 inline int Get_Ans(int x,int k){
34     int l=1,r=n,Mid;
35     while(l<=r){
36         Mid=l+r>>1;
37         if(Query(Rt[x],1,n,Mid)>=k)r=Mid-1;else l=Mid+1;
38     }
39     if(l>n)return -1;return b[l];
40 }
41 int main()
42 {
43     scanf("%d%d",&n,&m);
44     for(i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i,f[i]=i;
45     while(m--)scanf("%d%d",&x,&y),f[Find(x)]=Find(y);
46     for(i=1;i<=n;i++)Update(Rt[Find(i)],1,n,a[i]);
47     scanf("%d",&m);
48     while(m--){
49         scanf("%s%d%d",s,&x,&y);
50         if(s[0]=='Q')printf("%d\n",Get_Ans(Find(x),y));else{
51             f1=Find(x);f2=Find(y);
52             if(f1!=f2){
53                 f[f1]=f2;
54                 Rt[f2]=Merge(Rt[f1],Rt[f2]);
55             }
56         }
57     }
58     return 0;
59 }