题解

嗯对可能就是没看清数据范围卡了很久吧。。。

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,a[400100];
struct Tree{
    int l,r;unsigned long long sum,add;
}tree[1600010];
void build(unsigned long long p,unsigned long long l,unsigned long long r)
{
    tree[p].l=l;tree[p].r=r;
    if(l==r)
    {
        tree[p].sum=a[l];
        return;
    }
    unsigned long long mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void spread(unsigned long long p)
{
    if(tree[p].add)
    {
        tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
        tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
        tree[p*2].add+=tree[p].add;
        tree[p*2+1].add+=tree[p].add;
        tree[p].add=0;
    }
}
void change(unsigned long long p,unsigned long long l,unsigned long long r,long long d)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
        tree[p].sum+=(unsigned long long)d*(tree[p].r-tree[p].l+1);
        tree[p].add+=d;
        return;
    }
    spread(p);
    unsigned long long mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid)change(p*2,l,r,d);
    if(r>mid)change(p*2+1,l,r,d);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
unsigned long long qwq(unsigned long long p,unsigned long long l,unsigned long long r)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
        return tree[p].sum;
    }
    spread(p);
    unsigned long long mid=(tree[p].l+tree[p].r)>>1;
    unsigned long long ans=0;
    if(l<=mid)ans+=qwq(p*2,l,r);
    if(r>mid)ans+=qwq(p*2+1,l,r);
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    unsigned long long l,r,d,ask;
    for(int i=1;i<=m;i++)
    {
        cin>>ask;
        if(ask==1)
        {
            cin>>l>>r>>d;
            change(1,l,r,d);
        }
        else if(ask==2)
        {
            cin>>l>>r;
            printf("%lld\n",qwq(1,l,r));
        }
    }
    return 0;
}