SegmentTree.cc

#include <bits/stdc++.h>

using namespace std;

struct node {
    node *l, *r;
    int v, s, t = 0;
    node(int val = 0, int sz = 1, node *ls = NULL, node *rs = NULL):
            v(val), s(sz), l(ls), r(rs) {  }
} pool[200000];

node *get(const node &v) {
    static int t = 0;
    return &(pool[t++] = v);
}

void pushup(node *&cur) {
    while (cur->r == NULL || cur->l == NULL) {
        if (cur->r == NULL && cur->l == NULL) return;
        if (cur->r != NULL) cur = cur->r;
        else                cur = cur->l;
    }
    cur->s = cur->l->s + cur->r->s;
    cur->v = cur->l->v + cur->r->v;
}

void pushdown(node *cur) {
    if (cur->s == 1) {
        cur->t = 0;
        return;
    }
    cur->l->v += cur->t * cur->l->s;
    cur->r->v += cur->t * cur->r->s;
    cur->l->t += cur->t;
    cur->r->t += cur->t;
    cur->t = 0;
}

void insert(node *&cur, int p, int v) {
    if (cur == NULL) {
        cur = get(node(v));
        return;
    }
    pushdown(cur);
    if (cur->s == 1) {
        cur->l = get(node(p == 1 ? cur->v : v));
        cur->r = get(node(p == 0 ? cur->v : v));
        cur->v = cur->l->v + cur->r->v;
        cur->s = 2;
    } else {
        if (p < cur->l->s)
            insert(cur->l, p, v);
        else
            insert(cur->r, p - cur->l->s, v);
    }
    pushup(cur);
}

void remove(node *&cur, int p) {
    if (cur == NULL) return;
    if (cur->s == 1) {
        cur = NULL;
        return;
    }
    pushdown(cur);
    if (p < cur->l->s)
        remove(cur->l, p);
    else
        remove(cur->r, p - cur->l->s);
    pushup(cur);
}

void update(node *&cur, int l, int r, int v) {
    if (cur == NULL) return;
    if (l == 0 && r == cur->s) {
        cur->v += v * cur->s;
        cur->t += v;
        return;
    }
    pushdown(cur);
    int ss = cur->l->s;
    if (l < ss) update(cur->l, l, min(ss, r), v);
    if (r > ss) update(cur->r, max(l, ss) - ss, r - ss, v);
    pushup(cur);
}

int query(node *&cur, int l, int r) {
    if (cur == NULL) return 0;
    if (l == 0 && r == cur->s) return cur->v;
    pushdown(cur);
    int ss = cur->l->s, ans = 0;
    if (l < ss) ans += query(cur->l, l, min(ss, r));
    if (r > ss) ans += query(cur->r, max(l, ss) - ss, r - ss);
    return ans;
}

int main() {
    int n;
    node *rt = NULL;
    cin >> n;
    while ( n-- ) {
        int o, x, y, z;
        cin >> o >> x;
        switch (o) {
            case 1:
                cin >> y;
                insert(rt, x, y);
                break;
            case 2:
                remove(rt, x);
                break;
            case 3:
                cin >> y >> z;
                update(rt, x, y, z);
                break;
            case 4:
                cin >> y;
                cout << query(rt, x, y) << endl;
                break;
        }
    }
}