Description

维护一个序列，支持区间加，区间翻转，区间取最大值这三个操作。

Solution

Splay.

就是细节比较麻烦。

Code

#include 
    
     #include 
     
       const int N = 50000 + 10; int fa[N], ch[N][2], val[N], sz[N], rev[N], add[N], mx[N]; void upd(int x) {    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;    mx[x] = std::max(val[x], std::max(mx[ch[x][0]], mx[ch[x][1]]));}void pd(int x) {    if (rev[x]) {        std::swap(ch[x][0], ch[x][1]);        rev[ch[x][0]] ^= 1;        rev[ch[x][1]] ^= 1;        rev[x] = 0;    }    if (add[x]) {        if (ch[x][0]) val[ch[x][0]] += add[x], add[ch[x][0]] += add[x], mx[ch[x][0]] += add[x];        if (ch[x][1]) val[ch[x][1]] += add[x], add[ch[x][1]] += add[x], mx[ch[x][1]] += add[x];        add[x] = 0;    }}int dir(int x) { return x == ch[fa[x]][1]; }void rot(int x) {    int f = fa[x], d = dir(x);    if (fa[x] = fa[f]) ch[fa[x]][dir(f)] = x;    if (ch[f][d] = ch[x][d^1]) fa[ch[f][d]] = f;    ch[fa[f] = x][d^1] = f;    upd(f);    upd(x);}int st[N];void splay(int x, int t = 0) {    int top = 0, i;    for (i = x; fa[i]; i = fa[i]) st[top++] = fa[i];    while (top--) pd(st[top]);    pd(x);    for (; fa[x] != t; rot(x)) if (fa[fa[x]] != t) rot(dir(fa[x]) == dir(x) ? fa[x] : x);}int kth(int k, int t) {    int o = t;     while (1) {        pd(o);        if (sz[ch[o][0]] == k-1) break;        else if (sz[ch[o][0]] >= k) o = ch[o][0];        else { k -= sz[ch[o][0]] + 1; o = ch[o][1]; }    }    splay(o, fa[t]);    return o;}int n;void reverse(int l, int r) {    splay(1);    int y = kth(r+1, 1);    int x = ch[y][0];    kth(l-1, x);    rev[ch[ch[y][0]][1]] ^= 1;}void addval(int l, int r, int k) {    splay(1);         int y = kth(r+1, 1);    int x = ch[y][0];    kth(l-1, x);     add[ch[ch[y][0]][1]] += k;    val[ch[ch[y][0]][1]] += k;    mx[ch[ch[y][0]][1]] += k;}int query(int l, int r) {    splay(1);    int y = kth(r+1, 1);    int x = ch[y][0];    kth(l-1, x);    return mx[ch[ch[y][0]][1]];} void put(int o) {    if (!o) return;    put(ch[o][0]);    printf("%d %d %d\n", ch[o][0], ch[o][1], val[o]);    put(ch[o][1]); } int main() {    scanf("%d", &n);    for (int i = 1; i <= n+2; ++i) {        if (fa[i] = i-1) ch[i-1][1] = i;        sz[i] = n - i + 3;        val[i] = 0;    }    mx[0] = -2147483647;    val[n+1] = 0;    int m, l, r, v, op;    scanf("%d", &m);    while (m--) {        scanf("%d%d%d", &op, &l, &r);        if (op == 1) { scanf("%d", &v); addval(l+1, r+1, v); }        else if (op == 2) reverse(l+1, r+1);        else printf("%d\n", query(l+1, r+1));    }    return 0;}