fulinran2026 @ 2024-01-18 15:15:26

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;

int n,m,ans;
int a[N];
struct mm
{
    int l,r;
    int add,sum;
}tree[4*N+5];

void build(int k,int L,int R)
{
    tree[k].l=L;
    tree[k].r=R;
    if(L==R)
    {
        tree[k].sum=a[L];
        return ;
    }
    int mid=(L+R)/2;
    build(2*k,L,mid);
    build(2*k+1,mid+1,R);
    tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
}

void pushup(int k,int L,int R)
{
    if(R>L)
        tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
    tree[k].sum+=tree[k].add*(R-L+1);
}

void add(int k,int L,int R,int d)
{
    if(L>tree[k].r||R<tree[k].l) return ;
    if(L<=tree[k].l&&R>=tree[k].r)
    {
        tree[k].add+=d;
        return ;
    }
    add(2*k,L,R,d);
    add(2*k+1,L,R,d);
    pushup(k,L,R);
}

void ask(int k,int L,int R,int add)
{
    if(L>tree[k].r||R<tree[k].l) return ;
//  cout<<tree[k].l<<"_"<<tree[k].r<<" "<<ans<<"__"<<add<<"\n";
    if(L<=tree[k].l&&R>=tree[k].r)
    {
        ans+=tree[k].sum+add*(R-L+1)+tree[k].add;
//      cout<<tree[k].l<<"_"<<tree[k].r<<" "<<ans<<"__"<<tree[k].sum+add*(R-L+1)<<"\n";
        return ;
    }
    ask(2*k,L,R,add+tree[k].add);
    ask(2*k+1,L,R,add+tree[k].add);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int Num,x,y,k;
        scanf("%d",&Num);
        if(Num==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(1,x,y,k);
        }
        if(Num==2)
        {
            scanf("%d%d",&x,&y);
            ans=0;
            ask(1,x,y,0);
            printf("%d\n",ans);
        }
    }
    return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
*/

by fulinran2026 @ 2024-01-19 13:06:01

死因1：没写 pushdown

有图为证

死因2：没开 long long

有图为证

AC Code:

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;

const int N=2e5+5;

LL n,m,ans;
LL a[N];
struct mm
{
    LL l,r;
    LL add,sum;
}tree[4*N+5];

void build(LL k,LL L,LL R)
{
    tree[k].l=L;
    tree[k].r=R;
    if(L==R)
    {
        tree[k].sum=a[L];
        return ;
    }
    int mid=(L+R)/2;
    build(2*k,L,mid);
    build(2*k+1,mid+1,R);
    tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
}

void pushup(LL k)
{
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}

void pushdown(LL k)
{
    if(tree[k].add)
    {
        tree[k*2].add+=tree[k].add;
        tree[(k*2)+1].add+=tree[k].add;
        tree[k*2].sum+=(tree[k*2].r-tree[k*2].l+1)*tree[k].add;
        tree[(k*2)+1].sum+=(tree[(k*2)+1].r-tree[(k*2)+1].l+1)*tree[k].add;
        tree[k].add=0;
    }
}

void add(LL k,LL L,LL R,LL d)
{
    if(L>tree[k].r||R<tree[k].l) return ;
    if(L<=tree[k].l&&R>=tree[k].r)
    {
        tree[k].sum+=(tree[k].r-tree[k].l+1)*d;
        tree[k].add+=d;
        return ;
    }
    pushdown(k);
    add(2*k,L,R,d);
    add(2*k+1,L,R,d);
    pushup(k);
}

void ask(LL k,LL L,LL R)
{
    if(L>tree[k].r||R<tree[k].l) return ;
//  cout<<tree[k].l<<"_"<<tree[k].r<<" "<<ans<<"__"<<add<<" "<<(R-L+1)<<"\n";
    if(L<=tree[k].l&&R>=tree[k].r)
    {
        ans+=tree[k].sum;
        return ;
    }
    pushdown(k);
    ask(2*k,L,R);
    ask(2*k+1,L,R);
    pushup(k);
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int Num,x,y,k;
        scanf("%d",&Num);
        if(Num==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(1,x,y,k);
        }
        if(Num==2)
        {
            scanf("%d%d",&x,&y);
            ans=0;
            ask(1,x,y);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

*/