3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 15122 Solved: 6576
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
平衡树模板dearu；
↓代码（Splay）
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<cstdio> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<map> 10 #include<set> 11 #define N 100039 12 #define mod 20070831 13 #define inf 0x3f3f3f3f 14 #define ll long long 15 using namespace std; 16 struct poi 17 { 18 int fa,son[2],siz,cnt,n; 19 }tree[N]; 20 int tot,root; 21 inline int get(int x) 22 { 23 return tree[tree[x].fa].son[1]==x; 24 } 25 void update_size(int x) 26 { 27 tree[x].siz=tree[x].cnt+tree[tree[x].son[0]].siz+tree[tree[x].son[1]].siz; 28 } 29 void rotate(int x) 30 { 31 int fa=tree[x].fa,old=tree[fa].fa,wh=get(x),wa=get(fa); 32 tree[fa].son[wh]=tree[x].son[wh^1]; 33 tree[tree[fa].son[wh]].fa=fa; 34 tree[x].son[wh^1]=fa; 35 tree[fa].fa=x; 36 tree[old].son[wa]=x; 37 tree[x].fa=old; 38 update_size(fa); 39 } 40 void splay(int x) 41 { 42 int fa=tree[x].fa; 43 while(fa) 44 { 45 if(tree[fa].fa) 46 { 47 rotate(get(fa)==get(x) ? fa : x); 48 } 49 rotate(x); 50 fa=tree[x].fa; 51 } 52 root=x,update_size(x); 53 } 54 int query_rank(int x) 55 { 56 int now=root; 57 while(tree[now].n!=x) 58 { 59 now=tree[now].son[x>tree[now].n]; 60 } 61 splay(now); 62 return tree[tree[now].son[0]].siz+1; 63 } 64 int query_num(int x) 65 { 66 int now=root,stp; 67 while(39) 68 { 69 stp=tree[now].son[0]; 70 if(stp && x<=tree[stp].siz) 71 { 72 now=stp; 73 } 74 else 75 { 76 x-=(stp ? tree[stp].siz : 0)+tree[now].cnt; 77 if(x<=0) 78 { 79 return tree[now].n; 80 } 81 now=tree[now].son[1]; 82 } 83 } 84 } 85 int query_mae() 86 { 87 int now=tree[root].son[0]; 88 while(tree[now].son[1]) 89 { 90 now=tree[now].son[1]; 91 } 92 return now; 93 } 94 int query_ato() 95 { 96 int now=tree[root].son[1]; 97 while(tree[now].son[0]) 98 { 99 now=tree[now].son[0]; 100 } 101 return now; 102 } 103 void insert(int x) 104 { 105 if(!root) 106 { 107 tree[root=++tot]=(poi){0,{0,0},1,1,x}; 108 return; 109 } 110 int now=root,fa=0; 111 while(39) 112 { 113 if(x==tree[now].n) 114 { 115 tree[now].cnt++; splay(now); 116 return; 117 } 118 fa=now,now=tree[now].son[x>tree[now].n]; 119 if(!now) 120 { 121 tree[++tot]=(poi){fa,{0,0},1,1,x}; 122 tree[fa].son[x>tree[fa].n]=tot; 123 splay(tot); 124 return; 125 } 126 } 127 } 128 void del(int x) 129 { 130 int Sinogi=query_rank(x); 131 tree[root].cnt--; 132 if(!tree[root].cnt) 133 { 134 if(!tree[root].son[0] && !tree[root].son[1]) 135 { 136 root=0; 137 return; 138 } 139 int stp=-1; 140 stp= tree[root].son[0] ? stp : 1; 141 stp= tree[root].son[1] ? stp : 0; 142 if(stp!=-1) 143 { 144 root=tree[root].son[stp]; 145 tree[root].fa=0; 146 return; 147 } 148 stp=tree[root].son[1]; 149 splay(query_mae()); 150 tree[stp].fa=root; 151 tree[root].son[1]=stp; 152 update_size(root); 153 } 154 } 155 int main() 156 { 157 int n,opt,x; 158 scanf("%d",&n); 159 while(n--) 160 { 161 scanf("%d%d",&opt,&x); 162 switch(opt) 163 { 164 case 1: 165 insert(x); 166 break; 167 case 2: 168 del(x); 169 break; 170 case 3: 171 printf("%d\n",query_rank(x)); 172 break; 173 case 4: 174 printf("%d\n",query_num(x)); 175 break; 176 case 5: 177 insert(x); 178 printf("%d\n",tree[query_mae()].n); 179 del(x); 180 break; 181 case 6: 182 insert(x); 183 printf("%d\n",tree[query_ato()].n); 184 del(x); 185 break; 186 } 187 } 188 return 0; 189 }