苣蒻20分求助,疑似tag传不下去

P1253 扶苏的问题

Liyuqiao11 @ 2023-07-13 16:52:49

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define int long long
int n,m,a[N];
struct T{
    int l;
    int r;
    int maxn;
    int lazy;
    int tag;
}t[N*4];
void pushup(int i){
    t[i].maxn=max(t[i*2].maxn,t[i*2+1].maxn);
}
void pushdown(int i){
    if(t[i].l==t[i].r){
        t[i].lazy=-1e18;
        t[i].tag=0;
        return;
    }
    if(t[i].lazy!=-1e18){
        t[i*2].lazy=t[i].lazy;
        t[i*2].maxn=t[i].lazy;
        t[i*2+1].lazy=t[i].lazy;
        t[i*2+1].maxn=t[i].lazy;
        t[i*2].tag=0;
        t[i*2+1].tag=0;
        t[i].lazy=-1e18;
        return;
    }
    if(t[i].tag==0) return;
    t[i*2].maxn+=t[i].tag;
    t[i*2+1].maxn+=t[i].tag;
    t[i*2].tag+=t[i].tag;
    t[i*2+1].tag+=t[i].tag;
    return;
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    if(l==r){
        t[i].maxn=a[l];
        t[i].lazy=-1e18;
        t[i].tag=0;
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    pushup(i);
}
void update(int i,int l,int r,int x){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].lazy=x;
        t[i].maxn=x;
        t[i].tag=0;
        return;
    }
    pushdown(i);
    if(t[i*2].r>=l){
        update(i*2,l,r,x);
    }
    if(t[i*2+1].l<=r){
        update(i*2+1,l,r,x);
    }
    pushup(i);
}
void update_2(int i,int l,int r,int x){
    if(t[i].l>=l&&t[i].r<=r){
        t[i].tag+=x; 
        t[i].maxn+=x;
        return;
    }
    pushdown(i);
    if(t[i*2].r>=l){
        update_2(i*2,l,r,x);
    }
    if(t[i*2+1].l<=r){
        update_2(i*2+1,l,r,x);
    }
    pushup(i);
}
int query(int i,int l,int r){
    if(t[i].l>=l&&t[i].r<=r){
        return t[i].maxn;
    }
    pushdown(i);
    int ans=-1e18;
    if(t[i*2].r>=l){
        ans=max(ans,query(i*2,l,r));
    }
    if(t[i*2+1].l<=r){
        ans=max(ans,query(i*2+1,l,r));
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            update(1,x,y,k);
        }
        else if(op==2){
            cin>>x>>y>>k;
            update_2(1,x,y,k);
        }
        else{
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
}

by zhongshizhao1 @ 2023-08-07 20:54:39

首先建议你用“<<1”代替"2"并且用<<1|1代替2+1,能优化不少常数


by zhongshizhao1 @ 2023-08-07 20:55:08

2和2+1


|