POJ-3468 A Simple Problem with Integers (opens new window)

Splay模拟线段树即可

做这题时顺便发现了以前用的Splay树的小漏洞，已补上

#include <cstdio>
#include <iostream>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
//cuz i am not using ios
using namespace std;

const int maxn = 1e5 + 1000;
struct splay_tree{
    //六倍空间
    int child[maxn][2], fa[maxn], size[maxn];
    ll val[maxn], lazy[maxn], sum[maxn];

    int node_cnt, root;

    void add(int rt, ll delta){
        if(rt == 0) return;
        val[rt] += delta;
        sum[rt] += size[rt] * delta;
        lazy[rt] += delta;
    }

    void _push_up(int rt){
        sum[rt] = val[rt] + sum[child[rt][0]] + sum[child[rt][1]];
        size[rt] = size[child[rt][0]] + size[child[rt][1]] + 1;
    }

    void _push_down(int rt){
        if(lazy[rt] == 0) return;
        add(child[rt][0], lazy[rt]);
        add(child[rt][1], lazy[rt]);
        lazy[rt] = 0;
    }

    int _chk(int rt){return child[fa[rt]][1] == rt;}

    int _build(ll * init_val, int l, int r, int p){
        if(l > r) return 0;
        int idx = ++node_cnt;
        int mid = (l + r) >> 1;
        fa[idx] = p, val[idx] = init_val[mid];
        child[idx][0] = _build(init_val, l, mid - 1, idx);
        child[idx][1] = _build(init_val, mid + 1, r, idx);
        _push_up(idx);
        return idx;
    }

    void build(ll * init_val, int len){
        node_cnt = 0;
        child[0][0] = child[0][1] = val[0] = sum[0] = lazy[0] = size[0] = 0;
        root = _build(init_val, 0, len + 1, 0);
    }

    void rotate(int rt){
        int par = fa[rt], grandf = fa[par];
        int k = _chk(rt), op_child = child[rt][k ^ 1];
        child[grandf][_chk(par)] = rt, fa[rt] = grandf;
        child[par][k] = op_child, fa[op_child] = par;
        child[rt][k ^ 1] = par, fa[par] = rt;
        _push_up(par), _push_up(rt);
    }

    int find(int idx){
        int rt = root;
        while(rt){
            _push_down(rt);
            int sizel = size[child[rt][0]];
            if(sizel + 1 == idx) return rt;
            if(sizel >= idx) rt = child[rt][0];
            else idx -= sizel + 1, rt = child[rt][1];
        }
        return -10;
    }

    void splay(int rt, int goal = 0){
        while(fa[rt] != goal){
            if(fa[fa[rt]] != goal){
                if(_chk(rt) == _chk(fa[rt])) rotate(fa[rt]);
                else rotate(rt);
            }
            rotate(rt);
        }
        if(!goal) root = rt;
    }

    void interval_add(int l, int r, ll delta){
        r += 2;
        l = find(l), r = find(r);
        splay(l), splay(r, l);
        add(child[r][0], delta);
        _push_up(r), _push_up(l);
    }

    ll interval_query(int l, int r){
        r += 2;
        l = find(l), r = find(r);
        splay(l), splay(r, l);
        return sum[child[r][0]];
    }

}sp_tree;

ll init_val[maxn];

void solve(){
    // POJ上务必用scanf代替cin
    char buffer[20];
    ll n, q, a, b, c;
    scanf("%lld%lld", &n, &q);
    init_val[0] = init_val[n + 1] = 0;
    for(int i=1; i<=n; i++) scanf("%lld", &init_val[i]);
    sp_tree.build(init_val, n);
    for(int i=0; i<q; i++){
        scanf("%s%lld%lld", buffer, &a, &b);
        if(buffer[0] == 'C'){
            scanf("%lld", &c);
            sp_tree.interval_add(a, b, c);
        }else if(buffer[0] == 'Q'){
            cout << sp_tree.interval_query(a, b) << '\n';
        }
    }
}

signed main(){
    solve();
}