到底哪出问题了?

P3372 【模板】线段树 1

zqhbxsgs @ 2024-03-24 10:35:34

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100010],w[100010 * 4];
void pushup(int id){
    w[id] = w[id * 2] + w[id * 2 + 1];
}
void build(int id,int L,int R){
    if(L == R){
        w[id] = a[L];
        return ;
    }
    int M = (L + R) / 2;
    build(id * 2,L,M);
    build(id * 2 + 1,M + 1,R);
    pushup(id);
}
long long query1(int id,int L,int R,int p){
    if(L == R){
        return w[id];
    }
    int M = (L + R) / 2;
    if(M >= p){
        return query1(id * 2,L,M,p);
    }else{
        return query1(id * 2 + 1,M + 1,R,p);
    }
}
void update1(int id,int L,int R,int p,int x){
    if(L == R){
        w[id] = x;
    }else{
        int M = (L + R) / 2;
        if(M >= p){
            update1(id * 2,L,M,p,x);
        }else{
            update1(id * 2 + 1,M + 1,R,p,x);
        }
        pushup(id);
    }
}
bool inrange(int L,int R,int l,int r){
    return (l <= L) && (R <= r);
}
bool outofrange(int L,int R,int l,int r){
    return (L > r) || (R < l);
}
long long query(int id,int L,int R,int l,int r){
    if(inrange(L,R,l,r)){
        return w[id];
    }else if(!outofrange(L,R,l,r)){
        int M = (L + R) / 2;
        return query(id * 2,L,M,l,r) + query(id * 2 + 1,M + 1,R,l,r);
    }else{
        return 0;
    }
}
long long lzy[100010 * 4];
void maketag(int id,int len,long long x){
    lzy[id] += x;
    w[id] += len * x;
}
void pushdown(int id,int L,int R){
    int M = (L + R) / 2;
    maketag(id * 2,M - L + 1,lzy[id]);
    maketag(id * 2 + 1,R - M,lzy[id]);
    lzy[id] = 0;
}
long long query(int id,int L,int R,int l,int r,long long x){
    if(inrange(L,R,l,r)){
        return w[id];
    }else if(!outofrange(L,R,l,r)){
        int M = (L + R) / 2;
        pushdown(id,L,R); 
        return query(id * 2,L,M,l,r,x) + query(id * 2 + 1,M + 1,R,l,r,x);
    }else{
        return 0;
    }
}
void update(int id,int L,int R,int l,int r,long long x){
    if(inrange(L,R,l,r)){
        maketag(id,R - L + 1,x);
    }else if(!outofrange(L,R,l,r)){
        int M = (L + R) / 2;
        pushdown(id,L,R); 
        update(id * 2,L,M,l,r,x);
        update(id * 2 + 1,M + 1,R,l,r,x);
        pushup(id);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i = 1,op;i <= m;i ++){
        scanf("%d",&op);
        int x,y;
        long long k;
        if(op == 1){
            scanf("%d%d%lld",&x,&y,&k);
            update(1,1,n,x,y,k);
        }else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

|