[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 {
 11     x ^= y ^= x ^= y;
 12 }
 13 
 14 inline int Max(int x, int y)
 15 {
 16     return x > y ? x : y;
 17 }
 18 
 19 inline int get(int x)
 20 {
 21     return x == son[f[x]][1];
 22 }
 23 
 24 inline void update(int now)
 25 {
 26     if(now)
 27     {
 28         size[now] = 1;
 29         if(ls) size[now] += size[ls];
 30         if(rs) size[now] += size[rs];
 31         
 32         max[now] = key[now];
 33         if(ls) max[now] = Max(max[now], max[ls]);
 34         if(rs) max[now] = Max(max[now], max[rs]);
 35     }
 36 }
 37 
 38 inline void pushdown(int now)
 39 {
 40     if(rev[now])
 41     {
 42         swap(ls, rs);
 43         if(ls) rev[ls] ^= 1;
 44         if(rs) rev[rs] ^= 1;
 45         rev[now] = 0;
 46     }
 47     if(add[now])
 48     {
 49         if(ls) add[ls] += add[now], key[ls] += add[now], max[ls] += add[now];
 50         if(rs) add[rs] += add[now], key[rs] += add[now], max[rs] += add[now];
 51         add[now] = 0;
 52     }
 53 }
 54 
 55 inline void build(int x, int y, int fa, int &now)
 56 {
 57     if(x > y) return;
 58     int mid = (x + y) >> 1;
 59     now = ++cnt;
 60     f[now] = fa;
 61     build(x, mid - 1, now, ls);
 62     build(mid + 1, y, now, rs);
 63     update(now);
 64 }
 65 
 66 inline void rotate(int x)
 67 {
 68     pushdown(f[x]);
 69     pushdown(x);
 70     int old = f[x], oldf = f[old], wh = get(x);
 71     
 72     son[old][wh] = son[x][wh ^ 1];
 73     f[son[old][wh]] = old;
 74     
 75     if(oldf) son[oldf][old == son[oldf][1]] = x;
 76     f[x] = oldf;
 77     
 78     son[x][wh ^ 1] = old;
 79     f[old] = x;
 80     
 81     update(old);
 82     update(x);
 83 }
 84 
 85 inline void splay(int x, int to)
 86 {
 87     for(int fa; (fa = f[x]) != to; rotate(x))
 88         if(f[fa] != to)
 89             rotate(get(x) ^ get(fa) ? x : fa);
 90     if(!to) root = x;
 91 }
 92 
 93 inline int find(int x)
 94 {
 95     int now = root;
 96     while(1)
 97     {
 98         pushdown(now);
 99         if(x <= size[ls]) now = ls;
100         else
101         {
102             x -= size[ls];
103             if(x == 1) return now;
104             x--;
105             now = rs;
106         }
107     }
108 }
109 
110 int main()
111 {
112     int i, k, x, y, v;
113     scanf("%d %d", &n, &m);
114     a[1] = -INF, a[n + 2] = -INF;
115     build(1, n + 2, 0, root);
116     for(i = 1; i <= m; i++)
117     {
118         scanf("%d %d %d", &k, &x, &y);
119         x = find(x);
120         y = find(y + 2);
121         splay(x, 0);
122         splay(y, x);
123         if(k == 1)
124         {
125             scanf("%d", &v);
126             add[son[son[root][1]][0]] += v;
127             max[son[son[root][1]][0]] += v;
128             key[son[son[root][1]][0]] += v;
129             update(son[root][1]);
130             update(root);
131         }
132         else if(k == 2) rev[son[son[root][1]][0]] ^= 1;
133         else printf("%d
", max[son[son[root][1]][0]]);
134     }
135     return 0;
136 }
View Code