洛谷P4146 序列终结者 题解 splay tree

题目链接：https://www.luogu.com.cn/problem/P4146

题目大意：

支持：

• 区间更新（+x）
• 区间翻转
• 区间查询（最大值）

解题思路：几乎和 AcWing2437. Splay 这题一模一样。

示例程序：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
const int INF = (1LL<<60);

int n, m;
struct Node {
    int s[2], p, v;
    int sz, flag, mx, add;

    Node() {};
    Node(int _v, int _p) {v = _v; p = _p; s[0] = s[1] = 0; flag = 0; sz = 1; mx = v; add = 0;}
} tr[maxn];
int root, idx;

void push_up(int x) {
    tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1;
    tr[x].mx = max(tr[x].v, max(tr[tr[x].s[0]].mx, tr[tr[x].s[1]].mx));
}

void t_swap(int x) {
    tr[x].flag ^= 1;
    swap(tr[x].s[0], tr[x].s[1]);
}

void t_add(int x, int d) {
    tr[x].v += d;
    tr[x].mx += d;
    tr[x].add += d;
}

void push_down(int x) {
    if (tr[x].flag) {
        t_swap(tr[x].s[0]);
        t_swap(tr[x].s[1]);
        tr[x].flag = 0;
    }
    if (tr[x].add) {
        t_add(tr[x].s[0], tr[x].add);
        t_add(tr[x].s[1], tr[x].add);
        tr[x].add = 0;
    }
}

void f_s(int p, int u, bool k) {
    tr[p].s[k] = u;
    tr[u].p = p;
}

void rot(int x) {
    int y = tr[x].p, z = tr[y].p;
    bool k = tr[y].s[1] == x;
    f_s(z, x, tr[z].s[1]==y);
    f_s(y, tr[x].s[k^1], k);
    f_s(x, y, k^1);
    push_up(y), push_up(x);
}

void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            (tr[y].s[1]==x) ^ (tr[z].s[1]==y) ? rot(x) : rot(y);
        rot(x);
    }
    if (!k) root = x;
}

int get_k(int k) {
    int u = root;
    while (u) {
        push_down(u);
        if (tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].sz + 1 == k) return u;
        else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
    }
    return -1;
}

int build(int l, int r, int p) {
    int x = ++idx;
    int v = (l < 1 || l > n) ? -INF : 0;
    tr[x] = Node(v, p);
    int mid = (l + r) / 2;
    if (l < mid) tr[x].s[0] = build(l, mid-1, x);
    if (r > mid) tr[x].s[1] = build(mid+1, r, x);
    push_up(x);
    return x;
}

void init() {
    tr[0] = Node(0, 0);
    tr[0].sz = 0;
    tr[0].mx = -INF;
}

signed main() {
    init();
    cin >> n >> m;
    root = build(0, n+1, 0);
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        l = get_k(l), r = get_k(r+2);
        splay(l, 0), splay(r, l);
        push_down(l), push_down(r);
        if (op == 1) {
            cin >> x;
            t_add(tr[r].s[0], x);
        }
        else if (op == 2) {
            t_swap(tr[r].s[0]);
        }
        else {
            cout << tr[tr[r].s[0]].mx << endl;
        }
    }
    return 0;
}