[BZOJ3196] [Tyvj1730] 二逼平衡树（线段树 套 Splay）

传送门

至少BZOJ过了，其他的直接弃。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1.查询k在区间内的排名

2.查询区间内排名为k的值

3.修改某一位值上的数值

4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)

5.查询k在区间内的后继(后继定义为大于x，且最小的数)

最外层套一颗线段树，用来表示区间，线段树下面套个splay用来维护当前线段树节点的区间。

对于第二问可以二分，看看哪个数的排名为 k。

——代码

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define root 1, 1, n 5 #define lson now << 1, l, mid 6 #define rson now << 1 | 1, mid + 1, r 7 #define ls son[now][0] 8 #define rs son[now][1] 9 #define debug puts("**************"); 10 11 const int MAXN = 3500001, INF = 2147483647; 12 13 int n, m, sz; 14 int seq[MAXN], rt[MAXN]; 15 int f[MAXN], son[MAXN][2], cnt[MAXN], key[MAXN], size[MAXN]; 16 17 inline int read() 18 25 26 inline int max(int x, int y) 27 30 31 inline int min(int x, int y) 32 35 36 inline void Splay_clear(int now) 37 40 41 inline void Splay_update(int now) 42 49 } 50 51 inline int Splay_get(int x) 52 55 56 inline void Splay_rotate(int x) 57 72 73 inline void Splay_splay(int x) 74 79 80 inline void Splay_insert(int x, int k) 81 90 while(1) 91 100 fa = now; 101 now = son[now][k > key[now]]; 102 if(!now) 103 113 } 114 } 115 116 inline int Splay_findrank(int x, int k) 117 128 else now = ls; 129 } 130 } 131 132 inline int Splay_find(int x, int k) 133 145 } 146 } 147 148 inline int Splay_pre(int x) 149 154 155 inline int Splay_suc(int x) 156 161 162 inline void Splay_del(int x) 1 171 if(!ls && !rs) 172 177 if(!ls || !rs) 178 184 int pre = Splay_pre(x); 185 Splay_splay(pre); 186 rt[x] = pre; 187 son[pre][1] = rs; 188 f[rs] = pre; 189 Splay_clear(now); 190 Splay_update(pre); 191 } 192 193 inline int Splay_findpre(int x, int k) 194 203 else now = ls; 204 } 205 return ans; 206 } 207 208 inline int Splay_findsuc(int x, int k) 209 218 else now = rs; 219 } 220 return ans; 221 } 222 223 inline void SegTree_insert(int x, int k, int now, int l, int r) 224 231 232 inline int SegTree_askrank(int x, int y, int k, int now, int l, int r) 233 239 240 inline void SegTree_change(int x, int k, int now, int l, int r) 241 250 251 inline int SegTree_findpre(int x, int y, int k, int now, int l, int r) 252 258 259 inline int SegTree_findsuc(int x, int y, int k, int now, int l, int r) 260 266 267 int main() 268 286 case 2: 287 298 printf("%d\n", ans 1); 299 break; 300 } 301 case 3: 302 310 case 4: 311 318 case 5: 319 326 } 327 } 328 return 0; 329 }
View Code

上一篇：[luoguP1328] 生活大爆炸版石头剪刀布（模拟）

下一篇：[luoguP2957] [USACO09OCT]谷仓里的回声Barn Echoes（Hash）

---

线段树 splay 模板 树套树