求助(样例都不过)

P3372 【模板】线段树 1

mxjz666 @ 2024-03-31 21:43:14

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
const int N=1e5+10;
int a[4*N];
struct info{
    int maxv;
};
struct tr{
    int add;
};
info operator + (const info &x,const info &y){
    info cnt={max(x.maxv,y.maxv)};
    return cnt;
}
info operator + (const info &x,const tr &add){
    info cnt={x.maxv+add.add};
    return cnt;
}
tr operator + (const tr &x,const tr &y){
    tr cnt={x.add+y.add};
    return cnt;
}
struct node{
    tr t;
    info v;
}tree[4*N];
void update(int id){
    tree[id].v=tree[id*2].v+tree[id*2+1].v;
    return;
}
void tadd(int id,tr x){
    tree[id].v=tree[id].v+x;
    tree[id].t=tree[id].t+x;
    return;
}
void down(int id){
    if(tree[id].t.add!=0){
        tadd(id*2,tree[id].t);
        tadd(id*2+1,tree[id].t);
        tree[id].t.add=0;
    } 
    return;
}
void build(int id,int l,int r){
    if(l==r){
        tree[id].v={a[l]};
    }else{
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        update(id);
    }
    return;
}
void work(int id,int l,int r,int ql,int qr,tr val){
    if(l==r){
        tadd(id,val);
        return;
    }
    int mid=(l+r)/2;
    down(id);
    if(qr<=mid){
        work(id*2,l,mid,ql,qr,val);
    }else if(ql>mid){
        work(id*2+1,mid+1,r,ql,qr,val);
    }else{
        work(id*2,l,mid,ql,mid,val);
        work(id*2+1,mid+1,r,mid+1,qr,val);
    }
    update(id);
    return;
}
info qu(int id,int l,int r,int ql,int qr){
    if(l==ql&&r==qr){
        return tree[id].v;
    }
    int mid=(l+r)/2;
    down(id);
    if(qr<=mid){
        return qu(id*2,l,mid,ql,qr);
    }else if(ql>mid){
        return qu(id*2+1,mid+1,r,ql,qr);
    }else{
        return qu(id*2,l,mid,ql,mid)+qu(id*2+1,mid+1,r,mid+1,qr);
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int x;
        cin>>x;
        if(x==1){
            int y,z,k;
            cin>>y>>z>>k;
            work(1,1,n,y,z,{k});
        }else{
            int y,z;
            cin>>y>>z;
            auto ans=qu(1,1,n,y,z);
            cout<<ans.maxv<<endl;
        }
    }
    return 0;
}

|