243. 一个简单的整数问题2

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn =1e5+1;
typedef long long ll;
ll d[4*maxn],b[4*maxn],a[maxn],n,m,l,r,k;
string op;
void build(ll s,ll t,ll p)
{
    ll mid=(t+s)>>1;
    if(s==t)
    {
        d[p]=a[s];
        return ;
    }
    build(s,mid,p*2);
    build(mid+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}
void pushdown(ll s,ll t,ll p)
{
    ll m=(s+t)>>1;
    if(b[p])
    {
        d[p*2]+=(m-s+1)*b[p];
        d[p*2+1]+=(t-m)*b[p];
        b[p*2+1]+=b[p];b[p*2]+=b[p];
        b[p]=0;
    }
}
void add(ll l,ll r,ll c,ll s,ll t,ll p)
{
    ll mid=(s+t)>>1;
    if(l<=s&&t<=r)
    {
        d[p]+=(t-s+1)*c;
        b[p]+=c;
        return ;
    }
    pushdown(s,t,p);
    if(l<=mid)
        add(l,r,c,s,mid,p*2);
    if(r>mid)
        add(l,r,c,mid+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}
ll getsum(ll l,ll r,ll s,ll t,ll p)
{
    ll res=0;
    if(l<=s&&t<=r)
    {
        return d[p];
    }
    ll mid=(s+t)>>1;
    pushdown(s,t,p);
    if(l<=mid)
        res+=getsum(l,r,s,mid,p*2);
    if(r>mid)
        res+=getsum(l,r,mid+1,t,p*2+1);
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,n,1);
    while (m -- )
    {
        cin>>op;
        if(op=="Q")
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",getsum(l,r,1,n,1));
        }
        else
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            add(l,r,k,1,n,1);
        }
    }
    return 0;
}

Donate