2018年全国多校算法寒假训练营练习比赛（第五场）H Tree Recovery

Tree Recovery

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

链接：https://www.nowcoder.com/acm/contest/77/H

题目描述:进行区间求和，区间加减（线段树加懒惰标记）

输入

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100000+500;
long long a[maxn];
struct node
{
    long long l,r;
    long long date,add;
} T[maxn*4];
long long n,m;
long long ans=0;
void build(long long v,long long l,long long r)
{
    T[v].l=l,T[v].r=r;
    if(l==r)
    {
        T[v].date=a[l];
        return ;
    }
    long long mid = (l+r)>>1;
    build(v<<1,l,mid);
    build(v<<1|1,mid+1,r);
    T[v].date=T[v<<1].date+T[v<<1|1].date;
}
void add(long long v,long long l,long long r,long long value)
{
    T[v].date+=(r-l+1)*value;
    if(T[v].l==l&&T[v].r==r)
    {
        T[v].add+=value;
        return ;
    }
    if(T[v].add)
    {
        T[v<<1].date+=(T[v<<1].r-T[v<<1].l+1)*T[v].add;
        T[v<<1|1].date+=(T[v<<1|1].r-T[v<<1|1].l+1)*T[v].add;
        T[v<<1].add+=T[v].add;
        T[v<<1|1].add+=T[v].add;
        T[v].add=0;
    }
    long long mid=(T[v].l+T[v].r)>>1;
    if(r<=mid)
    {
        add(v<<1,l,r,value);
    }
    else
    {
        if(l>mid)
        {
            add(v<<1|1,l,r,value);
        }
        else
        {
            add(v<<1,l,mid,value);
            add(v<<1|1,mid+1,r,value);
        }
    }
}
void query(long long v,long long l,long long r)
{
    if(T[v].l==l&&T[v].r==r)
    {
        ans+=T[v].date;
        return ;
    }
    if(T[v].add)
    {
        T[v<<1].date+=(T[v<<1].r-T[v<<1].l+1)*T[v].add;
        T[v<<1|1].date+=(T[v<<1|1].r-T[v<<1|1].l+1)*T[v].add;
        T[v<<1].add+=T[v].add;
        T[v<<1|1].add+=T[v].add;
        T[v].add=0;
    }
    long long mid = (T[v].l+T[v].r)>>1;
    if(r<=mid)
    {
        query(v<<1,l,r);
    }
    else
    {
        if(l>mid)
            query(v<<1|1,l,r);
        else
        {
            query(v<<1,l,mid);
            query(v<<1|1,mid+1,r);
        }
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
        char s[2];
        long long x,y,z;
        scanf("%s",s);
        if(s[0]=='Q')
        {
            scanf("%lld%lld",&x,&y);
            ans=0;
            query(1,x,y);
            printf("%lld\n",ans);
        }
        else
        {
            scanf("%lld%lld%lld",&x,&y,&z);
            add(1,x,y,z);
        }
    }
    return 0;
}