POJ3580 SuperMemo

#include <cstdio>
#include <climits>

#include <algorithm>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct node {
    ll x, d, cnt, lazy;
    bool rev;
    node *ls, *rs;
};

typedef ll (*func)(node*&);

const int N = 100010, M = N;

int n, m;
ll arg;
ll arr[N];
char s[20];
node* root;

ll act(int l, int r, func f);
ll get_d(node*& p);
ll add(node*& p);
ll reverse(node*& p);
ll insert(node*& p);
ll remove(node*& p);
int get_cnt(node* p);
void update(node* p);
void push_down(node* p);
void splay(node*& p, int x);
void zig(node*& p);
void zag(node*& p);
void order(node* p);
node* build(int x, int y);

int main() {
    int x, y, a;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &arr[i]);
    root = build(-1, n + 1);
    scanf("%d", &m);
    while (m--) {
        scanf("%s %d", s, &x);
        switch (s[0]) {
        case 'A':
            scanf("%d%lld", &y, &arg);
            act(x, y, add);
            break;
        case 'I':
            act(x, x, insert);
            break;
        case 'D':
            act(x, x, remove);
            break;
        case 'M':
            scanf("%d", &y);
            printf("%lld\n", act(x, y, get_d));
            break;
        default:
            if (s[3] == 'E') {
                scanf("%d", &y);
                act(x, y, reverse);
            } else {
                scanf("%d%d", &y, &a);
                if (x > y)
                    swap(x, y);
                a %= y - x + 1;
                if (a < 0)
                    a += y - x + 1;
                if (a == 0)
                    break;
                LOG("ROTATE: %d\n", a);
                act(x, y, reverse);
                act(x, x + a - 1, reverse);
                act(x + a, y, reverse);
            }
        }
    }
    return 0;
}

void order(node* p) {
    if (!p)
        return;
    push_down(p);
    order(p->ls);
    printf(" %lld", p->x);
    order(p->rs);
}

ll act(int l, int r, func f) {
    l += 2;
    r += 2;
    push_down(root);
    splay(root, l - 1);
    push_down(root->rs);
    splay(root->rs, r - l + 2);
    push_down(root->rs->ls);
    int ret = f(root->rs->ls);
    update(root->rs);
    update(root);
    return ret;
}

node* build(int x, int y) {
    static node pool[N + M];
    static int cnt;
    if (x > y)
        return NULL;
    node* p = pool + cnt;
    ++cnt;
    int mid = (x + y) >> 1;
    p->cnt = y - x + 1;
    p->ls = build(x, mid - 1);
    if (mid >= 0)
        p->x = arr[mid];
    p->rs = build(mid + 1, y);
    p->d = min(p->x, min(get_d(p->ls), get_d(p->rs)));
    return p;
}

ll add(node*& p) {
    p->lazy += arg;
    return 0;
}

ll get_d(node*& p) {
    if (!p)
        return LLONG_MAX;
    return p->d + p->lazy;
}

ll reverse(node*& p) {
    p->rev ^= true;
    return 0;
}

ll insert(node*& p) {
    scanf("%lld", &arr[0]);
    p->rs = build(0, 0);
    update(p);
    ++n;
    return 0;
}

ll remove(node*& p) {
    p = NULL;
    --n;
    return 0;
}

inline void push_down(node* p) {
    if (p->ls) {
        p->ls->rev ^= p->rev;
        p->ls->lazy += p->lazy;
    }
    if (p->rs) {
        p->rs->rev ^= p->rev;
        p->rs->lazy += p->lazy;
    }
    if (p->rev)
        swap(p->ls, p->rs);
    p->rev = false;
    p->x += p->lazy;
    p->d += p->lazy;
    p->lazy = 0;
}

void update(node* p) {
    p->cnt = 1 + get_cnt(p->ls) + get_cnt(p->rs);
    p->d = min(p->x, min(get_d(p->ls), get_d(p->rs)));
}

inline int get_cnt(node* p)
{ return p ? p->cnt : 0; }

inline void zig(node*& p) {
    push_down(p);
    node* son = p->ls;
    push_down(son);
    p->ls = son->rs;
    son->rs = p;
    update(p);
    p = son;
    update(p);
}

inline void zag(node*& p) {
    push_down(p);
    node* son = p->rs;
    push_down(son);
    p->rs = son->ls;
    son->ls = p;
    update(p);
    p = son;
    update(p);
}

void splay(node*& p, int x) {
    push_down(p);
    if (x == get_cnt(p->ls) + 1)
        return;
    if (x <= get_cnt(p->ls)) {
        push_down(p->ls);
        if (x == get_cnt(p->ls->ls) + 1) {
            zig(p);
            return;
        }
        if (x <= get_cnt(p->ls->ls)) {
            splay(p->ls->ls, x);
            zig(p);
            zig(p);
            return;
        }
        splay(p->ls->rs, x - 1 - get_cnt(p->ls->ls));
        zag(p->ls);
        zig(p);
        return;
    }
    x -= 1 + get_cnt(p->ls);
    push_down(p->rs);
    if (x == get_cnt(p->rs->ls) + 1) {
        zag(p);
        return;
    }
    if (x <= get_cnt(p->rs->ls)) {
        splay(p->rs->ls, x);
        zig(p->rs);
        zag(p);
        return;
    }
    splay(p->rs->rs, x - 1 - get_cnt(p->rs->ls));
    zag(p);
    zag(p);
}