【splay】BZOJ1500 維修數列

S o u r c e : Source: Source:[NOI2005]維修數列

P r o b l e m : Problem: Problem:模闆題。Splay的一些基礎操作：插入/删除/求和/求最大子段和/翻轉

I d e a : Idea: Idea:

1.處理T[0],maintain時不能影響父親。

2.首尾放兩個哨兵，防止越界。

3.pushdown放到get_kth中，注意maintain的時機。

4.不會maintian到有lazy标志的點，在pushdown時已經維護過該點。

C o d e : Code: Code:

#include<bits/stdc++.h>
#define lson T[o].ch[0]
#define rson T[o].ch[1]
using namespace std;

inline int read(){
    char c = getchar(); int x = 0, f = 1;
    while(c<'0' || c>'9') { if(c == '-') f = -1; c = getchar(); }
    while(c>='0' && c<='9') { x = x*10+c-'0'; c = getchar(); }
    return x*f;
}

int max(const int &x, const int &y) { return x<y?y:x; }

const int INF = 0x3f3f3f3f;
const int N = 5e5+10;

int tot1, tot2, root, tra[N], a[N];

struct Node {
    int ch[2], val, fa, sz;
    int tag, flip, sum, ls, ms, rs;
}T[N];

int newNode(int val, int fa) {
    int o = tot2?tra[tot2--]:++tot1;
    T[o].val = val, T[o].fa = fa, T[o].sz = 1;
    T[o].tag = T[o].flip = lson = rson = 0;
    T[o].sum = T[o].ls = T[o].ms = T[o].rs = val;
    return o;
}

void Erase(int o) {
    if(!o) return;
    tra[++tot2] = o;
    Erase(lson); Erase(rson);
}

void Reverse(int o) {
    if(!o || T[o].tag) return;
    T[o].flip ^= 1;
    swap(lson, rson); swap(T[o].ls, T[o].rs);
}

void paint(int o, int qv) {
    if(!o) return;
    T[o].tag = 1, T[o].val = qv;
    T[o].sum = qv*T[o].sz; T[o].flip = 0;
    T[o].ls = T[o].rs = T[o].ms = max(qv, T[o].sum);
}

void pushdown(int o) {
    if(T[o].tag) {
        paint(lson, T[o].val);
        paint(rson, T[o].val);
        T[o].tag = 0;
    }
    if(T[o].flip) {
        Reverse(lson);
        Reverse(rson);
        T[o].flip = 0;
    }
}

void maintain(int o) {
    T[o].sz = T[lson].sz+T[rson].sz+1;
    T[o].sum = T[lson].sum+T[rson].sum+T[o].val;
    T[o].ms = max(max(T[lson].ms, T[rson].ms), max(0, T[lson].rs)+max(0, T[rson].ls)+T[o].val);
    T[o].ls = max(T[lson].ls, T[lson].sum+max(0, T[rson].ls)+T[o].val);
    T[o].rs = max(T[rson].rs, T[rson].sum+max(0, T[lson].rs)+T[o].val);
}

void Rotate(int x){
    int y = T[x].fa, z = T[y].fa, k = T[y].ch[1]==x;
    T[z].ch[T[z].ch[1]==y] = x; T[x].fa = z;
    T[y].ch[k] = T[x].ch[k^1]; T[T[x].ch[k^1]].fa = y;
    T[x].ch[k^1] = y, T[y].fa = x;
    maintain(y); maintain(x);
}

void splay(int x, int goal){
    while(T[x].fa != goal) {
        int y = T[x].fa, z = T[y].fa;
        if(z != goal){
            if((T[z].ch[0]==y)^(T[y].ch[0]==x)) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
    if(goal == 0) root = x;
}

int get_Kth(int k){
    int o = root;
    if(T[o].sz < k) return 0;
    for(;;) {
        pushdown(o);
        int t = T[lson].sz;
        if(k <= t) o = lson;
        else if(k == t+1) return o;
        else k -= t+1, o = rson;
    }
}

void build(int &o, int L, int R, int fa) {
    int M = (L+R)>>1;
    o = newNode(a[M], fa);
    if(L == R) return;
    if(L < M) build(lson, L, M-1, o);
    if(M < R) build(rson, M+1, R, o);
    maintain(o);
}

void Insert(int k, int n) {
    for(int i = 1; i <= n; i++) a[i] = read();
    int fa = get_Kth(k+1); splay(fa, 0);
    int u = get_Kth(k+2); splay(u, fa);
    build(T[u].ch[0], 1, n, u);
    maintain(u), maintain(fa);
}

int main() {
    T[0].sz = T[0].sum = tot1 = tot2 = 0;
    T[0].ls = T[0].ms = T[0].rs = -INF;
    a[1] = a[2] = -INF, build(root, 1, 2, 0);
    char s[20]; int n, m;
    n = read(), m = read();
    Insert(0, n);
    while(m--) {
        scanf("%s", s);
        if(s[2] == 'X') {
            printf("%d\n", T[root].ms);
            continue;
        }
        int pos = read(), tot = read();
        if(s[0] == 'I') Insert(pos, tot);
        else {
            int l = get_Kth(pos); splay(l, 0);
            int r = get_Kth(pos+tot+1); splay(r, l);
            int &x = T[r].ch[0];
            if(s[0] == 'D') Erase(x), x = 0;
            else if(s[0] == 'M') paint(x, read());
            else if(s[0] == 'R') Reverse(x);
            else if(s[0] == 'G') printf("%d\n", T[x].sum);
            maintain(r), maintain(l);
        }
    }
    return 0;
}