学步园

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8

using namespace std;

const int maxn = 1e5 + 10;

__int64 tree[maxn<<2];
__int64 col[maxn<<2];

void pushup(int rt)
{
        tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}

void pushdown(int rt, int len)
{
        if(col[rt])
        {
                col[rt<<1] += col[rt];
                col[rt<<1|1] += col[rt];
                tree[rt<<1] += (len - (len>>1)) * col[rt];
                tree[rt<<1|1] += (len>>1) * col[rt];
                col[rt] = 0;
        }
}

void build(int l, int r, int rt)
{
        if(l == r)
        {
                scanf("%I64d", &tree[rt]);
                return ;
        }
        int m = (l + r) >> 1;
        build(l, m, rt<<1);
        build(m+1, r, rt<<1|1);
        pushup(rt);
}

void update(int L, int R, __int64 add, int l, int r, int rt)
{
        if(L <= l && R >= r)
        {
                tree[rt] += (__int64)(r - l + 1) * add;
                col[rt] += add;
                return ;
        }
        pushdown(rt, r-l+1);
        int m = (l + r) >> 1;
        if(L <= m) update(L, R, add, l, m, rt<<1);
        if(R > m) update(L, R, add, m+1, r, rt<<1|1);
        pushup(rt);
}

__int64 query(int L, int R, int l, int r, int rt)
{
        if(L <= l && R >= r)
        {
                return tree[rt];
        }
        pushdown(rt, r-l+1);
        int m = (l + r) >> 1;
        __int64 ret = 0;
        if(L <= m) ret += query(L, R, l, m, rt<<1);
        if(R > m) ret += query(L, R, m+1, r, rt<<1|1);
        return ret;
}

int main()
{
        #ifdef BellWind
        freopen("B.in", "r", stdin);
        #endif // BellWind

        int n, q;

        while(~scanf("%d%d", &n, &q))
        {
                build(1, n, 1);
                memset(col, 0, sizeof(col));
                while(q--)
                {
                        char order[8];
                        int a, b, c;
                        scanf("%s", order);
                        if(order[0] == 'C')
                        {
                                scanf("%d%d%d", &a, &b, &c);
                                update(a, b, c, 1, n, 1);
                        }
                        if(order[0] == 'Q')
                        {
                                scanf("%d%d", &a, &b);
                                printf("%I64d\n", query(a, b, 1, n, 1));
                        }
                }
        }

        return 0;
}