P2710 数列/P2042 [NOI2005] 维护数列

题意（以 P2710 为例）

思路

使用 FHQ-Treap 进行求解，清晰明了。

1. 对于 insert，先将要插入的数建成一棵树，然后将这棵树放入 FHQ-Treap 中。
2. 对于 delete，将要删除的树分离出来，然后把剩下的部分合并即可，将删除的树的树根丢到废弃节点的栈中以备以后使用（节约空间，不然 MLE）。
3. 对于 reverse，给一个节点打上标签并立即交换，参考文艺平衡树代码。注意，如果存在 MAKE-SAME 操作的标签，那么不用反转，因为所有数字都是一样的。
4. 对于 make-same，将这个节点的 reverse 的标记清空（用不到，理由如上），给这个节点打上标记并立即更新结构体中所有数字。
5. 对于 get-sum，pushup 维护即可。
6. 对于 get，与普通平衡树的看排名为 \(x\) 的数字是什么类似。
7. 对于 max-sum，最大子段和，参考 GSS-1，注意这是平衡树，对于根节点的处理细节非常多。

代码

细节非常多，注意对废弃节点的处理。（代码以 P2710 为准）

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 500010;
const i64 inf = 1e18;

struct node {
    int l, r, size, rnd;
    int tag_same, tag_rev;
    i64 key, lsum, rsum, sum, ans;
} tr[N];

int rt, cnt;
int del_ver[N], top;
int n, m;
int a[N], sz_a;

int newnode(int key) {
    int idx;
    if (!top) idx = ++cnt;
    else {
        idx = del_ver[top];
        top--;
        if (tr[idx].l) del_ver[++top] = (tr[idx].l);
        if (tr[idx].r) del_ver[++top] = (tr[idx].r);
    }
    tr[idx].l = tr[idx].r = 0;
    tr[idx].rnd = rand();
    tr[idx].size = 1;
    tr[idx].tag_same = -1e9;
    tr[idx].tag_rev = 0;
    tr[idx].key = tr[idx].lsum = tr[idx].rsum = tr[idx].sum = tr[idx].ans = key;
    return idx;
}

void addtagrev(int u) {
    if (!u) return;
    if (tr[u].tag_same != -1e9) return;
    tr[u].tag_rev ^= 1;
    swap(tr[u].l, tr[u].r);
    swap(tr[u].lsum, tr[u].rsum);
}

void addtagsame(int u, int key) {
    if (!u) return;
    if (tr[u].tag_rev) tr[u].tag_rev = 0;
    tr[u].tag_same = tr[u].key = key;
    tr[u].sum = key * tr[u].size;
    tr[u].lsum = tr[u].rsum = tr[u].ans = max(tr[u].key, tr[u].sum);
}

void pushdown(int u) {
    if (tr[u].tag_same != -1e9) {
        tr[u].tag_rev = 0;
        addtagsame(tr[u].l, tr[u].tag_same);
        addtagsame(tr[u].r, tr[u].tag_same);
        tr[u].tag_same = -1e9;
    }
    if (tr[u].tag_rev) {
        addtagrev(tr[u].l);
        addtagrev(tr[u].r);
        tr[u].tag_rev = 0;
    }
}

void pushup(int u) {
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
    tr[u].lsum = max({tr[tr[u].l].lsum, tr[tr[u].l].sum + tr[u].key, tr[tr[u].l].sum + tr[tr[u].r].lsum + tr[u].key});
    tr[u].rsum = max({tr[tr[u].r].rsum, tr[tr[u].r].sum + tr[u].key, tr[tr[u].r].sum + tr[tr[u].l].rsum + tr[u].key});
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum + tr[u].key;
    tr[u].ans = max({tr[tr[u].l].ans, tr[tr[u].r].ans, tr[u].key, tr[tr[u].l].rsum + tr[u].key, tr[tr[u].r].lsum + tr[u].key, tr[tr[u].l].rsum + tr[u].key + tr[tr[u].r].lsum});
}

void split(int u, int sz, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }
    pushdown(u);
    if (tr[tr[u].l].size + 1 <= sz) {
        x = u;
        split(tr[u].r, sz - tr[tr[u].l].size - 1, tr[u].r, y);
    }
    else {
        y = u;
        split(tr[u].l, sz, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if ((!x) || (!y)) return x | y;
    if (tr[x].rnd < tr[y].rnd) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

void del(int l, int r) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    del_ver[++top] = (y);
    rt = merge(x, z);
}

int build(int l, int r) {
    if (l == r) return newnode(a[l]);
    int mid = (l + r) >> 1;
    int x = build(l, mid);
    int y = build(mid + 1, r);
    return merge(x, y);
}

void insert(int p) {
    int x, y;
    int rt2 = build(1, sz_a);
    split(rt, p, x, y);
    rt = merge(merge(x, rt2), y);
}

void make_same(int l, int r, int c) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    addtagsame(y, c);
    rt = merge(merge(x, y), z);
}

void reverse_arr(int l, int r) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    addtagrev(y);
    rt = merge(merge(x, y), z);
}

i64 get_sum(int l, int r) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    i64 ans = tr[y].sum;
    rt = merge(merge(x, y), z);
    return ans;
}

i64 get_max(int l, int r) {
    int x, y, z;
    split(rt, r, x, z);
    split(x, l - 1, x, y);
    i64 ans = tr[y].ans;
    rt = merge(merge(x, y), z);
    return ans;
}

int get_num(int u, int rk) {
    pushdown(u);
    if (tr[tr[u].l].size + 1 == rk) return tr[u].key;
    else if (tr[tr[u].l].size >= rk) return get_num(tr[u].l, rk);
    else return get_num(tr[u].r, rk - tr[tr[u].l].size - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    tr[0].lsum = tr[0].rsum = tr[0].ans = -inf;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sz_a = n;
    insert(0);

    string opt;
    int x, y, z;
    for (int T = 1; T <= m; T++) {
        cin >> opt;
        if (opt == "INSERT") {
            cin >> x >> sz_a;
            for (int i = 1; i <= sz_a; i++) cin >> a[i];
            insert(x);
        }
        else if (opt == "DELETE") {
            cin >> x >> y;
            del(x, x + y - 1);
        }
        else if (opt == "MAKE-SAME") {
            cin >> x >> y >> z;
            make_same(x, x + y - 1, z);
        }
        else if (opt == "REVERSE") {
            cin >> x >> y;
            reverse_arr(x, x + y - 1);
        }
        else if (opt == "GET-SUM") {
            cin >> x >> y;
            cout << get_sum(x, x + y - 1) << '\n';
        }
        else if (opt == "GET") {
            cin >> x;
            cout << get_num(rt, x) << '\n';
        }
        else {
            cin >> x >> y;
            cout << get_max(x, x + y - 1) << '\n';
        }
    }
    return 0;
}