文艺平衡树

有些平衡树可以实现区间操作，例如 Splay，FHQ。通过对区间打 tag 的方式，可以实现区间翻转和区间覆盖。

例题

P3391 【模板】文艺平衡树

模板代码

SplayFHQ

#include<iostream>
using namespace std;
const int N = 1E5 + 10;

int n, m, root, nn;
int val[N], chd[N][2], sz[N], tag[N], fa[N];

void push_up(int p){
    if(p != 0) sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void push_down(int p){
    if(tag[p] == 0) return;
    swap(chd[p][0], chd[p][1]);
    if(chd[p][0]) tag[chd[p][0]] ^= 1;
    if(chd[p][1]) tag[chd[p][1]] ^= 1;
    tag[p] = 0;
}

int build_tree(int l, int r, int f){
    if(l > r) return 0;
    int mid = (l + r) >> 1, p;
    val[++nn] = mid;
    p = nn;
    fa[p] = f;
    chd[p][0] = build_tree(l, mid - 1, p);
    chd[p][1] = build_tree(mid + 1, r, p);
    push_up(p);
    return p;
}

bool get(int x){
    return x == chd[fa[x]][1];
}

void rotate(int x){
    int y = fa[x], z = fa[y], d = get(x), w = chd[x][d ^ 1];
    fa[w] = y;
    chd[y][d] = w;
    fa[x] = z;
    if(z) chd[z][get(y)] = x;
    fa[y] = x;
    chd[x][d ^ 1] = y;
    push_up(y);
    push_up(x);
}

void splay(int x, int goal = 0){
    while(fa[x] != goal){
        int y = fa[x], z = fa[y];
        if(z != goal){
            if(get(x) == get(y)){
                rotate(y);
            } else{
                rotate(x);
            }
        }
        rotate(x);
    }
    if(goal == 0) root = x;
}

int kth(int x){
    int cur = root;
    while(1){
        push_down(cur);
        if(x <= sz[chd[cur][0]]){
            cur = chd[cur][0];
        } else if(x == sz[chd[cur][0]] + 1){
            splay(cur);
            return cur;
        } else{
            x -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
        }
    }
    return 0;
}

void turn(int l, int r){
    int x = kth(l);
    int y = kth(r + 2);
    splay(x);
    splay(y, x);
    tag[chd[y][0]] ^= 1;
}

void inOrder(int x){
    push_down(x);
    if(chd[x][0]) inOrder(chd[x][0]);
    if(1 <= val[x] && val[x] <= n) cout << val[x] << ' ';
    if(chd[x][1]) inOrder(chd[x][1]);
}

int main(){

    cin >> n >> m;
    root = build_tree(0, n + 1, 0);
    while(m--){
        int l, r;
        cin >> l >> r;
        turn(l, r);
    }
    inOrder(root);
    cout << endl;

    return 0;
}

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N = 1E5 + 10;

int n, m;

int root, nn;
int val[N], chd[N][2], pri[N], tag[N], sz[N];

int addNode(int v) {
    val[++nn] = v;
    pri[nn] = rand();
    sz[nn] = 1;
    return nn;
}

void push_up(int p) {
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void move_tag(int p) {
    tag[p] ^= 1;
    swap(chd[p][0], chd[p][1]);
}

void push_down(int p) {
    if(!tag[p]) return;
    move_tag(chd[p][0]);
    move_tag(chd[p][1]);
    tag[p] = 0;
}

void split(int cur, int v, int &x, int &y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

int dfs(int l, int r) {
    if(l == r) {
        return addNode(l);
    }
    int mid = (l + r) >> 1;
    return merge(dfs(l, mid), dfs(mid + 1, r));
}

void rever(int l, int r) {
    int x, y, z, w;
    split(root, r, w, z);
    split(w, l - 1, x, y);
    tag[y] ^= 1;
    swap(chd[y][0], chd[y][1]);
    root = merge(merge(x, y), z);
}

void print(int cur) {
    if(cur == 0) {
        return;
    }
    push_down(cur);
    print(chd[cur][0]);
    cout << val[cur] << ' ';
    print(chd[cur][1]);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    srand(time(NULL));

    cin >> n >> m;
    root = dfs(1, n);

    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        rever(l, r);
    }

    print(root);

    cout << endl;

    return 0;
}

P2042 [NOI2005] 维护数列

线段树的最大子段和操作，可以通过记录区间左右边缘的答案，来更新更大的区间，难点在于 push_up() 函数。

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N = 5E5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N];

int root, nn;
int val[N], chd[N][2], sz[N], sum[N], pri[N];
int lans[N], rans[N], ans[N], Max[N];;
int tag_rev[N], tag_mdf[N];

int pool[N], top;

void push_up(int p) {
    int lc = chd[p][0], rc = chd[p][1];
    sz[p] = sz[lc] + sz[rc] + 1;
    sum[p] = sum[lc] + sum[rc] + val[p];
    Max[p] = max(max(Max[chd[p][0]], Max[chd[p][1]]), val[p]);
    lans[p] = max(lans[lc], sum[lc] + val[p] + lans[rc]);
    rans[p] = max(rans[rc], sum[rc] + val[p] + rans[lc]);
    lans[p] = max(lans[p], 0ll);
    rans[p] = max(rans[p], 0ll);
    ans[p] = max(max(ans[lc], ans[rc]), max(lans[p], rans[p]));
    ans[p] = max(ans[p], sum[p]);
    ans[p] = max(ans[p], rans[lc] + lans[rc] + val[p]);
    ans[p] = max(ans[p], 0ll);
}

void move_tag_rev(int p) {
    swap(chd[p][0], chd[p][1]);
    swap(lans[p], rans[p]);
    tag_rev[p] ^= 1;
}

void move_tag_mdf(int p, int tg) {
    sum[p] = sz[p] * tg;
    Max[p] = tg;
    val[p] = tg;
    tag_mdf[p] = tg;
    lans[p] = rans[p] = ans[p] = (sum[p] > 0) ? sum[p] : 0;
}

void push_down(int p) {
    if(tag_rev[p] != 0) {
        move_tag_rev(chd[p][0]);
        move_tag_rev(chd[p][1]);
        tag_rev[p] = 0;
    }
    if(tag_mdf[p] != INF) {
        move_tag_mdf(chd[p][0], tag_mdf[p]);
        move_tag_mdf(chd[p][1], tag_mdf[p]);
        tag_mdf[p] = INF;
    }
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

void split(int cur, int v, int& x, int& y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int addNode(int v) {
    int pos;
    if(top != 0) {
        pos = pool[top--];
    } else {
        pos = ++nn;
    }
    val[pos] = sum[pos] = v;
    chd[pos][0] = chd[pos][1] = 0;
    Max[pos] = v;
    sz[pos] = 1;
    pri[pos] = rand();
    tag_rev[pos] = 0;
    lans[pos] = rans[pos] = ans[pos] = max(v, 0ll);
    return pos;
}

int makeTree(int l, int r, int* v) {
    if(l == r) {
        return addNode(v[l]);
    }
    int mid = (l + r) >> 1;
    return merge(makeTree(l, mid, v), makeTree(mid + 1, r, v));
}

void delTree(int p) {
    if(p == 0) return;
    delTree(chd[p][0]);
    delTree(chd[p][1]);
    pool[++top] = p;
}

signed main() {

    memset(tag_mdf, 0x3f, sizeof(tag_mdf));
    memset(Max, -0x3f, sizeof(Max));

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    root = makeTree(1, n, a);

    while(m--) {
        string op;
        cin >> op;
        if(op == "INSERT") {
            int pos, tot;
            cin >> pos >> tot;
            int c[tot + 10];
            for(int i = 1; i <= tot; i++) {
                cin >> c[i];
            }
            int y = makeTree(1, tot, c);
            int x, z;
            split(root, pos, x, z);
            root = merge(merge(x, y), z);
        } else if(op == "DELETE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            delTree(y);
            root = merge(x, z);
        } else if(op == "MAKE-SAME") {
            int pos, tot, c;
            cin >> pos >> tot >> c;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_mdf(y, c);
            root = merge(merge(x, y), z);
        } else if(op == "REVERSE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_rev(y);
            root = merge(merge(x, y), z);
        } else if(op == "GET-SUM") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            cout << sum[y] << endl;
            root = merge(merge(x, y), z);
        } else if(op == "MAX-SUM") {
            if(ans[root] == 0) {
                cout << Max[root] << endl;
            } else cout << ans[root] << endl;
        }
    }

    return 0;
}