BZOJ 1500——メンテナンスシーケンス

ダイナミックな最大サブセグメントと
splayですね.GSS 1について話しましょう.4つの値を維持します.1つはこの区間と(以下sumと言います)、1つは左から最大と(以下lsと言います)、右から最大と(以下rsと言います)、もう1つは最大区間と(mx)、では$ls=max(leftson->ls,leftson->sum+rightson->ls)$$rs=......$$sum=leftson->sum+rightson->sum$$mx=max(leftson->sum,max(rightson->sum,leftson->rs+rightson->ls))$$というようにして、木の中のいろいろな特判を伸ばして、1つも考えずにこの問題を少なくとも1つ選んでください

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
    Node *ch[2];
    int s, v, ls, rs, sum, ans, k, f;
   
    inline int cmp(int x){
        int o = 0;
        if(ch[0] != NULL){
            if(ch[0] -> s >= x) return 0;
            o += ch[0] -> s;
        }
        if(o + 1 == x) return -1;
        return 1;
    }
   
    inline void maintain(){
        int yy, yt;
       
        s = 1;
        if(ch[0]) s += ch[0] -> s;
        if(ch[1]) s += ch[1] -> s;
       
        sum = v;
        if(ch[0]) sum += ch[0] -> sum;
        if(ch[1]) sum += ch[1] -> sum;
       
        ls = -214748364;
        if(ch[0]) ls = max(ls, ch[0] -> ls);
        yy = v;
        if(ch[0]) yy += ch[0] -> sum;
        yt = 0;
        if(ch[1]) yt = ch[1] -> ls;
        ls = max(ls, max(yy, yy + yt));
       
        rs = -214748364;
        if(ch[1]) rs = max(rs, ch[1] -> rs);
        yy = v;
        if(ch[1]) yy += ch[1] -> sum;
        yt = 0;
        if(ch[0]) yt = ch[0] -> rs;
        rs = max(rs, max(yy, yy + yt));
       
        ans = v;
        if(ch[0]) ans = max(ans, ch[0] -> ans);
        if(ch[1]) ans = max(ans, ch[1] -> ans);
        yy = 0;
        if(ch[0]) yy = ch[0] -> rs;
        yt = 0;
        if(ch[1]) yt = ch[1] -> ls;
        ans = max(ans, max(yy + yt + v, max(yy + v, yt + v)));
        return;
    }
   
    inline void pushdown(){
        if(f == 1){
            if(ch[0]){
                swap(ch[0] -> ch[0], ch[0] -> ch[1]);
                ch[0] -> f ^= 1;
                swap(ch[0] -> ls, ch[0] -> rs);
            }
           
            if(ch[1]){
                swap(ch[1] -> ch[0], ch[1] -> ch[1]);
                ch[1] -> f ^= 1;
                swap(ch[1] -> ls, ch[1] -> rs);
            }
           
            f = 0;
        }
       
        if(k != -214748364){
            if(ch[0]){
                ch[0] -> f = 0;
                ch[0] -> v = k;
                ch[0] -> sum = ch[0] -> s * k;
                if(k > 0){
                    ch[0] -> ls = ch[0] -> rs = ch[0] -> ans = ch[0] -> s * k;
                }
                else{
                    ch[0] -> ls = ch[0] -> rs = ch[0] -> ans = k;
                }
                ch[0] -> k = k;
            }
           
            if(ch[1]){
                ch[1] -> f = 0;
                ch[1] -> v = k;
                ch[1] -> sum = ch[1] -> s * k;
                if(k > 0){
                    ch[1] -> ls = ch[1] -> rs = ch[1] -> ans = ch[1] -> s * k;
                }
                else{
                    ch[1] -> ls = ch[1] -> rs = ch[1] -> ans = k;
                }
                ch[1] -> k = k;
            }   
           
            k = -214748364;
        }
    }
   
};
struct splay_tree{
    int a[500000];
    int size;
    Node* p;
   
    inline void init(){
        size = 0;
        return;
    }
   
    inline void rotate(Node* &o, int d){
        Node *k = o -> ch[d ^ 1];
        k -> pushdown();
        o -> ch[d ^ 1] = k -> ch[d];
        k -> ch[d] = o;
        o -> maintain();
        k -> maintain();
        o = k;
        return;
    }
   
    inline void splay(Node* &o, int k){
        o -> pushdown();
        int d = o -> cmp(k);
        if(d == 1 && o -> ch[0] != NULL) k = k - o -> ch[0] -> s - 1;
        else if(d == 1) k --;
        if(d != -1){
            Node* w = o -> ch[d];
            w -> pushdown();
            int d2 = w -> cmp(k);
            int k2 = k;
            if(d2 != 0){
                k2 --;
                if(w -> ch[0] != NULL){
                    k2 -= w -> ch[0] -> s;
                }
            }
            if(d2 != -1){
                splay(w -> ch[d2], k2);
                if(d == d2) rotate(o, d ^ 1);
                else rotate(o -> ch[d], d);
            }
            rotate(o, d ^ 1);
        }
        o -> maintain();
        return;
    }
   
    inline Node* merge(Node *left, Node *right){
        if(left == NULL) return right;
        if(right == NULL) return left;
        splay(left, left -> s);
        left -> ch[1] = right;
        left -> maintain();
        return left;
    }
   
    inline void split(Node* &o, int k, Node* &left, Node* &right){
        if(k == 0){
            left = NULL;
            right = o;
            return;
        }
        splay(o, k);
        left = o;
        right = o -> ch[1];
        left -> ch[1] = NULL;
        left -> maintain();
        return;
    }
   
    inline void insert(Node* &o, int l, int r){
        if(r < l) return;
        int mid = (l + r) / 2;
        o = new Node();
        o -> ch[0] = o -> ch[1] = NULL;
        o -> v = a[mid];
        o -> f = 0;
        o -> k = -214748364;
        if(l != r){
            insert(o -> ch[0], l, mid - 1);
            insert(o -> ch[1], mid + 1, r);
        }
        o -> maintain();
        return;
    }
   
    inline void add(int pos, int tot){
        Node *left, *mid, *right;
        split(p, pos, left, right);
        insert(mid, 1, tot);
        p = merge(left, merge(mid, right));
        return;
    }
   
    inline void delete_splay_tree(Node* &o){
        if(o -> ch[0] != NULL) delete_splay_tree(o -> ch[0]);
        if(o -> ch[1] != NULL) delete_splay_tree(o -> ch[1]);
        delete o;
        return;
    }
   
    inline void Delete(int pos, int l){
        Node *left, *mid, *right;
        split(p, pos - 1, left, mid);
        split(mid, l, mid, right);
        delete_splay_tree(mid);
        left = merge(left, right);
        p = left;
        return;
    }
   
    inline void flip(Node* &o, int l, int r){
        Node *left, *mid, *right;
        split(p, l - 1, left, mid);
        split(mid, r, mid, right);
        swap(mid -> ch[0], mid -> ch[1]);
        mid -> f ^= 1;
        swap(mid -> ls, mid -> rs);
        p = merge(left, merge(mid, right));
        return;
    }
   
    inline void make_same(Node* &o, int l, int r, int c){
        Node *left, *mid, *right;
        split(p, l - 1, left, mid);
        split(mid, r, mid, right);
        mid -> v = c;
        mid -> sum = mid -> s * c;
        if(c > 0){
            mid -> ls = mid -> rs = mid -> ans = mid -> s * c;
        }
        else{
            mid -> ls = mid -> rs = mid -> ans = c;
        }
        mid -> k = c;
        p = merge(left, merge(mid, right));
        return;
    }
   
    inline int query_sum(Node* &o, int l, int r){
        if(r == 0) return 0;
        Node *left, *mid, *right;
        split(p, l - 1, left, mid);
        split(mid, r, mid, right);
        int ret = mid -> sum;
        p = merge(left, merge(mid, right));
        return ret;
    }
   
    inline int query_boss(Node* &o){
        return o -> ans;
    }
   
} wt;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &wt.a[i]);
    }
    wt.insert(wt.p, 1, n);
    char str[100];
    int pos, tot, c;
    for(int i = 1; i <= m; i ++){
        scanf("%s", str);
        if(str[0] == 'I'){
            scanf("%d%d", &pos, &tot);
            for(int j = 1; j <= tot; j ++) scanf("%d", &wt.a[j]);
            if(tot == 0) continue;
            wt.add(pos, tot);
        }
        else if(str[0] == 'D'){
            scanf("%d%d", &pos, &tot);
            if(tot == 0) continue;
            wt.Delete(pos, tot);
        }
        else if(str[2] == 'K'){
            scanf("%d%d%d", &pos, &tot, &c);
            if(tot == 0) continue;
            wt.make_same(wt.p, pos, tot, c);
        }
        else if(str[0] == 'R'){
            scanf("%d%d", &pos, &tot);
            if(tot == 0) continue;
            wt.flip(wt.p, pos, tot);
        }
        else if(str[0] == 'G'){
            scanf("%d%d", &pos, &tot);
            printf("%d
", wt.query_sum(wt.p, pos, tot));
        }
        else{
            int ret = wt.query_boss(wt.p);
            printf("%d
", ret);
        }
        //printf("%d:%d
", i, wt.p -> s);
    }
    return 0;
}