哪里有问题

P3372 【模板】线段树 1

Willan_Lian @ 2023-11-17 17:45:57

代码如下:


#include<bits/stdc++.h>
using namespace std;
int n,m;
int A[100010];
long long C[400010];
long long b[400010];
long long Ans=0;
void insert(int lr,int rr,int idx) {
    if(lr==rr) {
        C[idx]=A[lr];
        return ;
    }
    int mid=lr+(rr-lr>>1);
    insert(lr,mid,idx*2);
    insert(mid+1,rr,idx*2+1);
    C[idx]=C[idx*2]+C[idx*2+1];
}

long long Sum(int lr,int rr,int ST,int ED,int idx) {
    if(lr<=ST && ED<=rr) return C[idx];
    int mid=ST+(ED-ST>>1);
    long long Ans=0;

    if(lr<=mid) Ans+=Sum(lr,rr,ST,mid,idx*2);
    if(rr>mid) Ans+=Sum(lr,rr,mid+1,ED,idx*2+1);
    return Ans;
}

void update(int lr, int rr, int ST, int ED, int idx,long long d){
    if(lr<=ST && ED<=rr){
        C[idx]+=(ED-ST+1)*d;
        b[idx]+=d;
        return;
    }
    int mid=ST+((ED-ST)>>1);
    if(b[idx] && ST!=ED){
        C[idx*2]+=b[idx]*(mid-ST+1);
        C[idx*2+1]+=b[idx]*(ED-mid);

        b[idx*2]+=b[idx],b[idx*2+1]+=b[idx];
        b[idx]=0;
    }

    if(lr<=mid) update(lr,rr,ST,mid,idx*2,d);
    if(rr>mid) update(lr,rr,mid+1,ED,idx*2+1,d);
    C[idx]=C[idx*2]+C[idx*2+1];
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&A[i]);
    insert(1,n,1);

    for(int i=1; i<=m; i++){
        int x;
        scanf("%d",&x);
        if(x==1){
            int y,z;
            long long w;
            scanf("%d%d%lld",&y,&z,&w);
            update(y,z,1,n,1,w);
        }

        if(x==2){
            int y,z;
            scanf("%d%d",&y,&z);
            printf("%lld\n",Sum(y,z,1,n,1));
        }
    }
    return 0;
}

by zdc_ @ 2023-11-17 18:19:50

在 Sum 函数里也需要懒标记下传吧


|