原题地址
http://ybt.ssoier.cn:8088/problem_show.php?pid=1548

#include <iostream>
#include <cstdio>
using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

namespace LineTree
{
    #define lc(n) ((n)<<1)
    #define rc(n) (((n)<<1)|1)
    #define pushup(n) sum[(n)]=sum[lc((n))]+sum[rc((n))]

    const int MAXN=4e6+128;

    long long sum[MAXN],tag[MAXN];

    int build(int u,int l,int r,long long num[])
    {
        if(l==r)    return sum[u]=num[l];
        int mid = (l+r)>>1;
        build(lc(u),l,mid,num);
        build(rc(u),mid+1,r,num);
        pushup(u);
    }

    inline void f(int u,int l,int r,long long offest)
    {
        tag[u]+=offest;
        sum[u]+=offest*(r-l+1);
    }

    inline void pushdown(int u,int l,int r)
    {
        if(tag[u]==0)   return ;
        int mid=(l+r)>>1;
        f(lc(u),l,mid,tag[u]);
        f(rc(u),mid+1,r,tag[u]);
        tag[u]=0;
    }

    inline void update(int x,int y,int l,int r,int u,long long offest)
    {
        if(x<=l && r<=y)
        {
            f(u,l,r,offest);
            return ;
        }

        pushdown(u,l,r);
        int mid=(l+r)>>1;
        if(x<=mid) update(x,y,l,mid,lc(u),offest);
        if(y>=mid+1) update(x,y,mid+1,r,rc(u),offest);
        pushup(u);
    }

    long long query(int x,int y,int l,int r,int u)
    {
        long long ans=0;
        if(x<=l && y>=r)    return sum[u];
        int mid=(l+r)>>1;
        pushdown(u,l,r);

        if(x<=mid)  ans+=query(x,y,l,mid,lc(u));
        if(y>=mid+1)    ans+=query(x,y,mid+1,r,rc(u));
        return ans;
    }
}


int n,q;

long long a[LineTree::MAXN];

int main()
{
    n=read();q=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    LineTree::build(1,1,n,a);
    for(int i=1;i<=q;i++)
    {
        int k=read();
        if(k==1)
        {
            int l,r,offest;
            l=read();r=read();offest=read();
            LineTree::update(l,r,1,n,1,offest);
        }   else{
            int l,r;
            l=read();r=read();
            printf("%lld\n",LineTree::query(l,r,1,n,1));
        }
    }
}
Last modification:April 30th, 2021 at 08:30 pm