首页 > 代码库 > 【pb_ds】【平衡树启发式合并】【并查集】bzoj2733 [HNOI2012]永无乡
【pb_ds】【平衡树启发式合并】【并查集】bzoj2733 [HNOI2012]永无乡
用并查集维护联通性。对每个联通块维护一个平衡树。合并时启发式合并。比较懒,用了pb_ds。
1 #include<cstdio> 2 #include<ext/pb_ds/assoc_container.hpp> 3 #include<ext/pb_ds/tree_policy.hpp> 4 using namespace std; 5 using namespace __gnu_cxx; 6 using namespace __gnu_pbds; 7 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T[100001]; 8 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator it; 9 int num[100001],val[100001],fa[100001],rank[100001];10 int n,m,q,x,y,f1,f2;11 char op[2];12 int Res,Num;char C,CH[20];13 inline int G()14 {15 Res=0;C=‘*‘; 16 while(C<‘0‘||C>‘9‘)C=getchar();17 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}18 return Res;19 }20 inline void P(int x)21 {22 Num=0;while(x>0)CH[++Num]=x%10,x/=10;23 while(Num)putchar(CH[Num--]+48);24 putchar(‘\n‘);25 }26 void init()27 {28 for(int i=1;i<=n;i++)29 fa[i]=i;30 }31 int findroot(int x) 32 {33 if(fa[x]==x)34 return x;35 int rt=findroot(fa[x]);36 fa[x]=rt;37 return rt;38 }39 void Union(const int &u,const int &v)40 {41 if(rank[u]<rank[v])42 {43 fa[u]=v;44 for(it=T[u].begin();it!=T[u].end();it++)45 T[v].insert((*it));46 T[u].clear();47 }48 else49 {50 fa[v]=u;51 for(it=T[v].begin();it!=T[v].end();it++)52 T[u].insert((*it));53 T[v].clear();54 if(rank[u]==rank[v]) rank[u]++;55 }56 }57 int main()58 {59 n=G();m=G();60 init();61 for(int i=1;i<=n;i++)62 {63 val[i]=G();64 T[i].insert(val[i]);65 num[val[i]]=i;66 }67 for(int i=1;i<=m;i++)68 {69 x=G();y=G();70 f1=findroot(x),f2=findroot(y);71 if(f1!=f2) Union(f1,f2);72 }73 q=G();74 for(int i=1;i<=q;i++)75 {76 scanf("%s",op);x=G();y=G();77 if(op[0]==‘Q‘)78 {79 f1=findroot(x);80 if(T[f1].size()<y) puts("-1");81 else P(num[*T[f1].find_by_order(y-1)]);82 }83 else84 {85 f1=findroot(x),f2=findroot(y);86 if(f1!=f2) Union(f1,f2);87 }88 }89 return 0;90 }
【pb_ds】【平衡树启发式合并】【并查集】bzoj2733 [HNOI2012]永无乡
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。