首页 > 代码库 > 平衡树
平衡树
平衡树
神奇的cxlove有一颗平衡树，其树之神奇无法用语言来描述 OrzOrz。 这棵树支持3种操作： 1、加入一个数到树中，维护平衡树的合法性； 2、给一个数X，用O(1)的时间求出来树中的数Y使得 Y ^ X 最大（异或操作， Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1） 3、给一个数X，用O(1)的时间求出来树中的数Y使得 Y ^ X 最小（异或操作， Pascal 写作 xor , 0 ^ 0 = 0 , 1 ^ 1 = 0 , 0 ^ 1 = 1 , 1 ^ 0 = 1 , 2 ^ 3 = 1） 请你帮忙实现这颗树。 cxlove由于过于牛，有些事情是无法做到的，你能在1s以内通过就好了。 最后补充一句，cxlove是世界冠军！
Input
第一行是数据组数T (T ≤ 100)。
对于每组数据，第一行是操作数N (N ≤ 10000)。
以下 N 行，每行一个字符串一个数字，分别代表：
- insert X ，加入数 X
- qmax X ，求第2种操作的答案
- qmin X ，求第3种操作的答案
输入保证不存在空树Query的情况 (1 ≤ X ≤ 1e9)
Output
对于操作 2 , 3 输出相应的答案。
Sample Input
14insert 1insert 2qmin 1qmax 1Sample Output
03Hint
Huge input and output. Please do not use: 1. cin ans cout of C++ 2. scanner of Java(Maybe BufferedReader is quicker)
//题目还够吓人的:我还以为真是什么平衡树，不会写呢，这不就是标准的字典树模板题吗。。。
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <string.h> 5 using namespace std; 6 #define MX 105 7 8 struct Node 9 { 10 Node * l,*r; 11 Node() 12 { 13 l=r=NULL; 14 } 15 }head; 16 int n; 17 18 void Init(Node * x) 19 { 20 if (x->l!=NULL) 21 Init(x->l); 22 if (x->r!=NULL) 23 Init(x->r); 24 delete (x->l); 25 delete (x->r); 26 } 27 28 void add(int x) 29 { 30 int w[50]; 31 int k=0; 32 while (x) 33 { 34 w[k++]=x%2; 35 x/=2; 36 } 37 while(k<30) w[k++]=0; 38 Node * p = &head; 39 for (int i=k-1;i>=0;i--) 40 { 41 if (w[i]==0) 42 { 43 if (p->l==NULL) 44 p->l = new(Node); 45 p = p->l; 46 } 47 else 48 { 49 if (p->r==NULL) 50 p->r = new(Node); 51 p = p->r; 52 } 53 } 54 } 55 56 int ans[50]; 57 void Find(int x[]) 58 { 59 Node *p =&head; 60 for (int i=29;i>=0;i--) 61 { 62 if (x[i]==0) 63 { 64 if (p->l==NULL) 65 { 66 ans[i]=1; 67 p=p->r; 68 } 69 else 70 { 71 ans[i]=0; 72 p=p->l; 73 } 74 } 75 else // 1 76 { 77 if (p->r==NULL) 78 { 79 ans[i]=0; 80 p=p->l; 81 } 82 else 83 { 84 ans[i]=1; 85 p=p->r; 86 } 87 } 88 } 89 } 90 91 void Mi(int x) 92 { 93 int xxx=x; 94 int w[50]; 95 int k=0; 96 while (x) 97 { 98 w[k++]=x%2; 99 x/=2;100 }101 while(k<30) w[k++]=0;102 Find(w);103 int res=0;104 int flag=1;105 for (int i=0;i<30;i++)106 {107 res+=flag*ans[i];108 flag*=2;109 }110 printf("%d\n",res^xxx);111 }112 113 void MA(int x)114 {115 int xxx=x;116 int w[50];117 int k=0;118 while (x)119 {120 w[k++]=!(x%2);121 x/=2;122 }123 while(k<30) w[k++]=1;124 Find(w);125 int res=0;126 int flag=1;127 for (int i=0;i<30;i++)128 {129 res+=flag*ans[i];130 flag*=2;131 }132 printf("%d\n",res^xxx);133 }134 135 int main()136 {137 int T;138 cin>>T;139 while (T--)140 {141 scanf("%d",&n);142 Init(&head);143 head.l=head.r=NULL;144 char op[50];145 for (int i=0;i<n;i++)146 {147 int tmp;148 scanf("%s",op);149 if (op[0]==‘i‘)150 {151 scanf("%d",&tmp);152 add(tmp);153 }154 else if (op[2]==‘i‘)155 {156 scanf("%d",&tmp);157 Mi(tmp);158 }159 else if (op[2]==‘a‘)160 {161 scanf("%d",&tmp);162 MA(tmp);163 }164 }165 }166 return 0;167 }
平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。