解题思路

由区间翻转问题接触到 Splay，学会之后这道题就是 Splay 的基本操作了。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100001;
const int INF = 0x3f3f3f3f;

struct node {
    int v, max, lazy, size, son[2];
    bool rev;
    void Init(int value) {
        v = max = value;
        size = 1;
        lazy = rev = son[0] = son[1] = 0;
    }
} t[MAXN];
int fa[MAXN], root;

void PushUp(int x) {
    t[x].max = t[x].v;
    t[x].size = 1;
    if(t[x].son[0]) {
        t[x].max = max(t[x].max, t[t[x].son[0]].max);
        t[x].size += t[t[x].son[0]].size;
    }
    if(t[x].son[1]) {
        t[x].max = max(t[x].max, t[t[x].son[1]].max);
        t[x].size += t[t[x].son[1]].size;
    }
}

void PushDown(int x) {
    if(x == 0) return;
    if(t[x].lazy) {
        if(t[x].son[0]) {
            t[t[x].son[0]].v += t[x].lazy;
            t[t[x].son[0]].max += t[x].lazy;
            t[t[x].son[0]].lazy += t[x].lazy;
        }
        if(t[x].son[1]) {
            t[t[x].son[1]].v += t[x].lazy;
            t[t[x].son[1]].max += t[x].lazy;
            t[t[x].son[1]].lazy += t[x].lazy;
        }
        t[x].lazy = 0;
    }
    if(t[x].rev) {
        if(t[x].son[0]) t[t[x].son[0]].rev ^= 1;
        if(t[x].son[1]) t[t[x].son[1]].rev ^= 1;
        swap(t[x].son[0], t[x].son[1]);
        t[x].rev = 0;
    }
}

void Rotate(int x, int type) {
    int y = fa[x], z = fa[y];
    t[y].son[!type] = t[x].son[type];
    fa[t[x].son[type]] = y;
    t[x].son[type] = y;
    fa[y] = x;
    t[z].son[t[z].son[1]==y] = x;
    fa[x] = z;
    PushUp(y);
}

void Splay(int x, int goal) {
    if(x == goal) return;
    while(fa[x] != goal) {
        int y = fa[x], z = fa[y];
        PushDown(z);
        PushDown(y);
        PushDown(x);
        int rx = t[y].son[0]==x;
        int ry = t[z].son[0]==y;
        if(z == goal) Rotate(x, rx);
        else {
            if(rx == ry) Rotate(y, ry);
            else Rotate(x, rx);
            Rotate(x, ry);
        }
    }
    PushUp(x);
    if(goal == 0) root = x;
}

int Find(int pos) {
    int u = root;
    PushDown(u);
    while(t[t[u].son[0]].size != pos) {
        if(pos < t[t[u].son[0]].size) u = t[u].son[0];
        else {
            pos -= t[t[u].son[0]].size+1;
            u = t[u].son[1];
        }
        PushDown(u);
    }

    return u;
}

void Update(int l, int r, int value) {
    int u = Find(l-1), v = Find(r+1);
    Splay(u, 0);
    Splay(v, u);
    t[t[v].son[0]].max += value;
    t[t[v].son[0]].v += value;
    t[t[v].son[0]].lazy += value;
}

void Reverse(int l, int r) {
    int u = Find(l-1), v = Find(r+1);
    Splay(u, 0);
    Splay(v, u);
    t[t[v].son[0]].rev ^= 1;
}

int Query(int l, int r) {
    int u = Find(l-1), v = Find(r+1);
    Splay(u, 0);
    Splay(v, u);

    return t[t[v].son[0]].max;
}

int Build(int l, int r) {
    if(l > r) return 0;
    if(l == r) return l;
    int m = (l+r) >> 1;
    int lson, rson;
    t[m].son[0] = lson = Build(l, m-1);
    t[m].son[1] = rson = Build(m+1, r);
    fa[lson] = fa[rson] = m;
    PushUp(m);

    return m;
}

void Init(int n) {
    t[0].Init(-INF);
    t[1].Init(-INF);
    t[n+2].Init(-INF);
    for(int i=2; i<=n+1; ++i) {
        t[i].Init(0);
    }
    root = Build(1, n+2), fa[root] = 0;
    fa[0] = 0;
    t[0].son[1] = root;
    t[0].size = 0;
}

int main(int argc, char const *argv[]) {
    int n, m, a, b, c, d;
    scanf("%d %d", &n, &m);
    Init(n);
    while(m--) {
        scanf("%d", &a);
        if(a == 1) {
            scanf("%d %d %d", &b, &c, &d);
            Update(b, c, d);
        }
        else if(a == 2) {
            scanf("%d %d", &b, &c);
            Reverse(b, c);
        }
        else {
            scanf("%d %d", &b, &c);
            printf("%d\n", Query(b, c));
        }
    }
    
    return 0;
}