0分求调orz

P3372 【模板】线段树 1

shadow_lgd @ 2023-11-26 11:35:27

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

int n,m;
int a[N],sum[N*4],lazy[N*4],ans[N*4];

void build(int v,int l,int r)
{
    int mid=(l+r)>>1;
    lazy[v]=0;
    if(l==r){
        sum[v]=a[l];
        return ;
    }
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    sum[v]=sum[v*2]+sum[v*2+1];
}
void pushdown(int v,int l,int r)//下放懒标记函数
{
    int mid=(l+r)/2;
    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];
    sum[2*v]+=lazy[v]*(mid-l+1);//[l,mid] 区间长度mid-l+1 
    sum[2*v+1]+=lazy[v]*(r-mid);//[mid+1,r] 区间长度r-mid
    lazy[v]=0; 
 } 
void Modify(int v,int l,int r,int x,int y,int k)//v表示当前区间编号 
{
    int mid=(l+r)/2;//l表示当前区间左端点,r表示当前区间右端点
    if(x<=l&&r<=y){
        sum[v]+=(r-l+1)*k;
        lazy[v]+=k;
        return ;
    }
    if(lazy[v]) pushdown(v,l,r);//判断当前区间是否有懒标记 
    if(x<=mid) Modify(v*2,l,mid,x,y,k);
    if(y>mid) Modify(v*2+1,mid+1,r,x,y,k);
    sum[v]=sum[v*2]+sum[v*2+1];
}
int Query(int v,int l,int r,int x,int y)
{
    int mid=(l+r)/2,k=0;
    if(x<=l&&r<=y)
        return sum[v];
    if(lazy[v]) pushdown(v,l,r);
    if(x<=mid) k=Query(v*2,l,mid,x,y);
    if(y>mid) k+=Query(v*2+1,mid+1,r,x,y);
    return k;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    int i=0;
    while(m!=0){
        int op,x,y,k;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1){
            scanf("&d",&k);
            Modify(1,1,n,x,y,k);
        }
        else{
            ans[i]=Query(1,1,n,x,y);
            i++;
        }
        m--;
    }
    for(int j=0;j<i;j++)
        cout << ans[j] << endl;
    return 0;
 } 

|