记录编号	352138	评测结果	AAAAAAAAAA
题目名称	magictree	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.409 s
提交时间	2016-11-16 21:30:25	内存使用	110.12 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
inline LL fast_read()
{
    LL r;
    char c;
    bool s = false;
    while(c = getchar())
    {
        if(c == '-')s = true;
        else if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
}
#define MAXN 2000001
struct node
{
    int l, r;
    int ls, rs;
    LL sum;
    LL lazyadd;
    void add(LL v)
    {
        lazyadd += v;
        sum += (r-l+1)*v;
    }
}ns[MAXN<<1];
int last = 1;
#define ld ns[d.ls]
#define rd ns[d.rs]
inline void pushup(node &d)
{
    d.sum = ld.sum + rd.sum;
}
int build(int l, int r)
{
    if(l > r)return 0;
    int c = last++;
    node &d = ns[c];
    d.l = l;
    d.r = r;
    if(l == r)d.sum = fast_read();
    else
    {
        int m = (l+r)>>1;
        d.ls = build(l, m);
        d.rs = build(m+1, r);
        pushup(d);
    }
    return c;
}
void pushdown(node &d)
{
    if(d.lazyadd)
    {
        ld.add(d.lazyadd);
        rd.add(d.lazyadd);
        d.lazyadd = 0;
    }
}
LL query(int c, int l, int r)
{
    if(!c)return 0;
    node &d = ns[c];
    if(d.l == l && d.r == r)return d.sum;
    else
    {
        pushdown(d);
        if(l >= rd.l)return query(d.rs, l, r);
        else if(r <= ld.r)return query(d.ls, l, r);
        else
            return query(d.ls, l, ld.r)+query(d.rs, rd.l, r);
    }
}
void addval(int c, int l, int r, LL v)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && d.r == r)
        d.add(v);
    else
    {
        pushdown(d);
        if(l >= rd.l)addval(d.rs, l, r, v);
        else if(r <= ld.r)addval(d.ls, l, r, v);
        else
        {
            addval(d.ls, l, ld.r, v);
            addval(d.rs, rd.l, r, v);
        }
        pushup(d);
    }
}
int main()
{
    freopen("magictree.in", "r", stdin);
    freopen("magictree.out", "w", stdout);
    int n, m;
    n = (int)fast_read();
    m = (int)fast_read();
    build(0, n-1);
    while(m--)
    {
        char c;
        while(!isalpha(c = getchar()));
        if(c == 'Q')
        {
            int l = (int)fast_read();
            int r = (int)fast_read();
            printf("%lld\n", query(1, l, r));
        }else if(c == 'C')
        {
            int l = (int)fast_read();
            int r = (int)fast_read();
            LL v = fast_read();
            addval(1, l, r, v);
        }
    }
    return 0;
}