传送门
支持操作：
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
上一篇：[luoguP1631] 序列合并（堆 || 优先队列）
下一篇：考后总结
splay 平衡树
