首页 > 代码库 > HNOI2012永无乡

HNOI2012永无乡

2024-07-20 07:24:20   215人阅读

题意：一个有n个节点的图，每个节点有一个重要度，每次操作可以连接两个节点或者查询与v连通的节点中重要度第k大的节点编号。

 

这一题依旧是平衡树，难度也不算高，连通性可以用并查集来解决，查询第k大的值则用平衡树实现，一开始建n棵平衡树，然后每次连接两个属于不同集合的节点的时候就在并查集中将它们合并，并且合并这两棵平衡树，为了保证时间复杂度，采用启发式合并，就是将规模较小的平衡树中的每个值插入到规模较大的平衡树中。考虑每一个节点，每次合并它所在的平衡树的规模至少扩大两倍（因为是将较小的插入到较大的平衡树中），那么它最多操作 log(n)次，每次时间复杂度为O(log(n))，总时间复杂度为O(nα(n)+nlog^2(n))，可以通过本题的数据。(PS:题目中要求是正整数，但刚看了数据9里面有一组0 0，所以在初始化的时候记得把0加上)

  1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4 #include <cctype>  5 #include <algorithm>  6 using namespace std;  7 const int inf=~0u>>1;  8 int father[100010];  9 int n,m; 10 int a[100010]; 11 int find(int x){ 12     if (father[x]!=x) father[x]=find(father[x]); 13     return father[x];     14 } 15 struct node { 16     int val,weight,size; 17     node *ch[2]; 18     node(int key=0,node *t=NULL) { 19         ch[0]=ch[1]=t; 20         val=key;weight=rand(); 21         size=1; 22     } 23     void maintain() { 24         size=ch[0]->size+ch[1]->size+1;     25     }         26 }*null,*root[100010]; 27 void rot (node *&t,int d){ 28     node *c=t->ch[d]; 29     t->ch[d]=c->ch[!d]; 30     c->ch[!d]=t; 31     t->maintain();c->maintain(); 32     t=c;     33 } 34 void insert(node *&t,int key){ 35     if (t==null) { 36         t=new node(key,null); return ; 37     } 38     int d=a[key]>a[t->val]; 39     insert(t->ch[d],key); 40     t->maintain(); 41 } 42 int select(node *t,int k){ 43     if (k>t->size) return -1; 44     if (t->ch[0]->size+1==k) return t->val; 45     if (k<=t->ch[0]->size) return select(t->ch[0],k); 46     return select(t->ch[1],k-t->ch[0]->size-1);     47 } 48 int readint(){ 49     char ch=getchar();int ret=0; 50     while (!isdigit(ch)) ch=getchar(); 51     while (isdigit(ch)){ 52         ret=ret*10+ch-‘0‘;     53         ch=getchar();     54     }     55     return ret; 56 } 57 char readchar(){ 58     char ch=getchar(); 59     while (!isalpha(ch)) ch=getchar(); 60     return ch;     61 } 62 void removetree(node *&t1,node *&t2){ 63     if (t1==null) return ; 64     insert(t2,t1->val); 65     removetree(t1->ch[0],t2); 66     removetree(t1->ch[1],t2); 67     delete t1; 68     t1=null;     69 } 70 void merge(int x,int y){ 71     int fx=find(x),fy=find(y);     72     if (root[fx]->size<root[fy]->size){ 73         father[fx]=fy; 74         removetree(root[fx],root[fy]); 75     }else { 76         father[fy]=fx; 77         removetree(root[fy],root[fx]);     78     } 79 } 80 int main(){ 81     srand(19961111); 82     null=new node; 83     null->size=0;null->weight=inf; 84     n=readint();m=readint(); 85     for (int i=0;i<=n;i++) { 86         father[i]=i; root[i]=null; 87     } 88     for (int i=1;i<=n;i++){ 89         a[i]=readint(); 90         insert(root[i],i); 91     } 92     int v1,v2; 93     while (m--){ 94         v1=readint();v2=readint(); 95         merge(v1,v2); 96     } 97     int p; 98     p=readint(); 99     while (p--){100         if (readchar()==‘B‘) {101             v1=readint();v2=readint();102             merge(v1,v2);103         }else {104             v1=readint();v2=readint();105             printf("%d\n",select(root[find(v1)],v2));106         }107     }108     return 0;109 }

 

HNOI2012永无乡


联系
我们