(Sky OJ) 92. 大榕樹的咒語

https://pc2.tfcis.org/sky/index.php/problem/view/92/

Treap~~

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

#define int long long

const int INF = 1e15 + 7;

struct Val {
    int lmax,rmax,midmax,sum;
    void rev() {
        swap(lmax,rmax);
    }
};

Val operator+(const Val &v1,const Val &v2) {
    Val ret;
    ret.lmax = max(v1.lmax,v1.sum+v2.lmax);
    ret.rmax = max(v2.rmax,v2.sum+v1.rmax);
    ret.midmax = max(max(v1.midmax,v2.midmax),v1.rmax + v2.lmax);
    ret.sum = v1.sum + v2.sum;
    return ret;
}

const int MAX_N = 4500006;

struct Treap {
    static Treap mem[MAX_N];
    Treap *lc,*rc;
    int sz,key,tag,pri;
    bool rev;
    Val val;
    Treap(){
        
    }
    Treap(int _val) : sz(1),key(_val),pri(rand()),tag(INF),rev(0),val({_val,_val,_val,_val}),lc(NULL),rc(NULL) {
        
    }
} Treap::mem[MAX_N],*ptr=Treap::mem;

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = 1;
    t->val = {t->key,t->key,t->key,t->key};
    if (t->lc) {
        t->val = t->lc->val +t->val;
        t->sz += t->lc->sz;
    }
    if (t->rc) {
        t->val = t->val + t->rc->val;
        t->sz += t->rc->sz;
    }
}

void push(Treap* t) {
    if (!t) return;
    if (t->rev) {
        if (t->lc) {
            swap(t->lc->lc,t->lc->rc);
            t->lc->rev ^= t->rev;
            t->lc->val.rev();
        }
        if (t->rc) {
            swap(t->rc->lc,t->rc->rc);
            t->rc->rev ^= t->rev;
            t->rc->val.rev();
        }
        t->rev ^= 1;
    }
    if (t->tag == INF) return;
    if (t->lc) {
        t->lc->tag = t->lc->key = t->tag;
        t->lc->val = {max(t->tag,t->lc->sz*t->tag),max(t->tag,t->lc->sz*t->tag),max(t->tag,t->lc->sz*t->tag),t->lc->sz*t->tag};
    }
    if (t->rc) {
        t->rc->tag = t->rc->key = t->tag;
        t->rc->val = {max(t->tag,t->rc->sz*t->tag),max(t->tag,t->rc->sz*t->tag),max(t->tag,t->rc->sz*t->tag),t->rc->sz*t->tag};
    }
    t->tag = INF;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        push(a);
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        push(b);
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) {
        a=b=NULL;
        return;
    }
    push(t);
    if (Sz(t->lc) + 1 <= k) {
        a=t;
        split(t->rc,k - Sz(t->lc) - 1,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    srand(time(NULL));
    Treap* root=NULL;
    int n,m;
    cin >> n >> m;
    for (int i=1;n>=i;i++) {
        int x;
        cin >> x;
        root=merge(root,new(++ptr)Treap(x));
    }
    while (m--) {
        string s;
        cin >>s;
        if (s=="MAX-SUM") {
            if (root!=NULL)cout<<root->val.midmax<<'\n';
            else cout<<0<<'\n';
        }
        else if (s=="GET-SUM") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            if (root != NULL)cout<<root->val.sum<<'\n';
            else cout<<0<<'\n';
            root=merge(merge(tl,root),tr);
        }
        else if (s=="REVERSE") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root->rev ^= 1;
            swap(root->lc,root->rc);
            root->val.rev();
            root=merge(tl,merge(root,tr));
        }
        else if (s=="DELETE") {
            int p,k;
            cin >> p >> k;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root=merge(tl,tr);
        }
        else if (s=="INSERT") {
            int p,k;
            cin >> p >> k;
            Treap* tl;
            split(root,p,tl,root);
            while (k--) {
                int x;
                cin >>x;
                tl=merge(tl,new(++ptr)Treap(x));
            }
            root=merge(tl,root);
        }
        else if (s=="MAKE-SAME") {
            int p,k,l;
            cin >> p >> k >> l;
            Treap *tl,*tr;
            split(root,p-1,tl,root);
            split(root,k,root,tr);
            root->tag = l;
            root->val = {max(root->tag,root->sz*root->tag),max(root->tag,root->sz*root->tag),max(root->tag,root->sz*root->tag),root->sz*root->tag};
            root->key = root->tag;
            root=merge(tl,merge(root,tr));
        }
    }
}