[codevs4655] 序列终结者（Splay）

传送门

支持操作：

1.区间加

2.区间翻转

3.区间求最大值

splay模板

注意：update 里更新 max 时需要取 3 个值的 Max

　　　别忘了各种边界讨论

——代码

1 #include <cstdio> 2 #define ls son[now][0] 3 #define rs son[now][1] 4 5 const int MAXN = 50010, INF = 2e9; 6 int n, m, root, cnt; 7 int a[MAXN], size[MAXN], key[MAXN], add[MAXN], max[MAXN], rev[MAXN], f[MAXN], son[MAXN][2]; 8 9 inline void swap(int &x, int &y) 10 13 14 inline int Max(int x, int y) 15 18 19 inline int get(int x) 20 23 24 inline void update(int now) 25 36 } 37 38 inline void pushdown(int now) 39 47 if(add[now]) 48 53 } 54 55 inline void build(int x, int y, int fa, int &now) 56 65 66 inline void rotate(int x) 67 84 85 inline void splay(int x, int to) 86 92 93 inline int find(int x) 94 107 } 108 } 109 110 int main() 111 132 else if(k == 2) rev[son[son[root][1]][0]] ^= 1; 133 else printf("%d\n", max[son[son[root][1]][0]]); 134 } 135 return 0; 136 }
View Code

上一篇：考后总结

下一篇：[luoguP2146] 软件包管理器（树链剖分）

---

splay 平衡树