【題解】POJ 3580 SuperMemo

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define nullptr NULL

struct Treap{
    int val;
    int pri;
    int sz;
    int mn;
    int add;
    bool rev;
    Treap* l;
    Treap* r;
    Treap(int x = 0){
        val = x;
        pri = (rand()<<16)|rand();
        sz = 1;
        mn = x;
        add = 0;
        rev = false;
        l = nullptr;
        r = nullptr;
    }
};
int Size(Treap* t){
    if (!t) return 0;
    return t->sz;
}
int Min(Treap *t){
    if (!t) return 1e9;
    return t->mn;
}
void pull(Treap* t){
    t->sz = Size(t->l) + Size(t->r) +1;
    t->mn = min(min(Min(t->l), Min(t->r)), t->val);
}
void push(Treap *t){
    if (t->rev){
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
        t->rev = false;
    }
    if (t->add){
        if (t->l){
            t->l->val += t->add;
            t->l->mn += t->add;
            t->l->add += t->add;
        }
        if (t->r){
            t->r->val += t->add;
            t->r->mn += t->add;
            t->r->add += t->add;
        }
        t->add = 0;
    }
}
Treap* Merge(Treap* a, Treap* b){
    if (!a || !b){
        if (!a) return b;
        else return a;
    }
    if (a->pri > b->pri){
        push(a);
        a->r = Merge(a->r, b);
        pull(a);
        return a;
    }
    else{
        push(b);
        b->l = Merge(a, b->l);
        pull(b);
        return b;
    }
}
void SplitBySize(Treap* t, int k, Treap*&a, Treap*&b){
    if (!t){
        a = nullptr;
        b = nullptr;
        return;
    }
    push(t);
    if (Size(t->l) < k){
        k -= Size(t->l)+1;
        a = t;
        SplitBySize(t->r, k, a->r, b);
        pull(a);
    }
    else{
        b = t;
        SplitBySize(t->l, k, a, b->l);
        pull(b);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    string s;
    Treap* root = nullptr;
    cin >> n;
    for (int i = 0, x; i < n; i++){
        cin >> x;
        root = Merge(root, new Treap(x));
    }
    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> s;
        if (s == "INSERT"){
            int x, p;
            cin >> x >> p;
            Treap *a, *b;
            SplitBySize(root, x, a, b);
            a = Merge(a, new Treap(p));
            root = Merge(a, b);
        }
        else if (s == "DELETE"){
            int x;
            cin >> x;
            Treap *a, *b, *c;
            SplitBySize(root, x-1, a, b);
            SplitBySize(b, 1, c, b);
            root = Merge(a, b);
        }
        else if (s == "MIN"){
            int x, y;
            cin >> x >> y;
            Treap *a, *b, *c;
            SplitBySize(root, x-1, a, b);
            SplitBySize(b, y-x+1, b, c);
            cout << b->mn << "\n";
            b = Merge(b, c);
            root = Merge(a, b);
        }
        else if (s == "REVOLVE"){
            int x, y, t;
            cin >> x >> y >> t;
            t %= (y-x+1);
            Treap *a, *b, *c, *d;
            SplitBySize(root, x-1, a, b);
            SplitBySize(b, y-x+1, b, d);
            SplitBySize(b, y-x+1-t, b, c);
            a = Merge(a, c);
            a = Merge(a, b);
            root = Merge(a, d);
        }
        else if (s == "REVERSE"){
            int x, y;
            cin >> x >> y;
            Treap *a, *b, *c;
            SplitBySize(root, x-1, a, b);
            SplitBySize(b, y-x+1, b, c);
            b->rev ^= 1;
            b = Merge(b, c);
            root = Merge(a, b);
        }
        else if (s == "ADD"){
            int x, y, d;
            cin >> x >> y >> d;
            Treap *a, *b, *c;
            SplitBySize(root, x-1, a, b);
            SplitBySize(b, y-x+1, b, c);
            b->add += d;
            b->mn += d;
            b->val += d;
            b = Merge(b, c);
            root = Merge(a, b);
        }
    }
}