60分求助

P1253 扶苏的问题

qinyi2022 @ 2024-03-28 20:39:31

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+1;
struct node{
    int l,r;
    bool vis_rep;
    ll Max,lazy,rep;
}t[N*4];
int n,q;
ll a[N];
void pushup(int p){
    t[p].Max = max(t[p<<1].Max,t[p<<1|1].Max);
}
void pushdown_rep(int p){
    if(t[p].vis_rep){
        t[p<<1].rep = t[p<<1|1].rep = t[p].rep;
        t[p<<1].Max = t[p<<1|1].Max = t[p].rep;
        t[p<<1].vis_rep = t[p<<1|1].vis_rep = 1;
        t[p<<1].lazy = t[p<<1|1].lazy = 0;
        t[p].vis_rep = t[p].rep = 0;
    }
}
void pushdown_add(int p){
    pushdown_rep(p);
    if(t[p].lazy){
        t[p<<1].lazy += t[p].lazy;
        t[p<<1|1].lazy += t[p].lazy;    
        t[p<<1].Max += t[p].lazy;
        t[p<<1|1].Max += t[p].lazy;
        t[p].lazy = 0;
    }
}
void build(int p,int l,int r){
    t[p].l = l;
    t[p].r = r;
    if(l == r){
        t[p].Max = a[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void addchange(int p,int L,int R,ll k){
    if(t[p].l >= L && t[p].r <= R){
        pushdown_rep(p); 
        t[p].lazy += k;
        t[p].Max += k;
        return;
    }
    pushdown_rep(p);
    pushdown_add(p);
    int mid = (t[p].l + t[p].r)>>1;
    if(mid >= L) addchange(p<<1,L,R,k);
    if(mid < R) addchange(p<<1|1,L,R,k);
    pushup(p);
}
void repchange(int p,int L,int R,ll k){
    if(t[p].l >= L && t[p].r <= R){
        t[p].rep = t[p].Max = k;
        t[p].vis_rep = 1; 
        t[p].lazy = 0;
        return;
    }
    pushdown_rep(p);
    int mid = (t[p].l + t[p].r)>>1;
    if(mid >= L) repchange(p<<1,L,R,k);
    if(mid < R) repchange(p<<1|1,L,R,k);
    pushup(p);
}
ll ask(int p,int L,int R){
    ll ans = LONG_LONG_MIN;
    if(t[p].l >= L && t[p].r <= R) return t[p].Max;
    pushdown_rep(p);
    pushdown_add(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if(mid >= L) ans = max(ans,ask(p<<1,L,R));
    if(mid < R) ans = max(ans,ask(p<<1|1,L,R));
    return ans;
}
int main(){
    cin >> n >> q;
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i = 1;i <= q;++i){
        int k,l,r;
        ll z;
        scanf("%d%d%d",&k,&l,&r);
        if(k == 1){
            scanf("%lld",&z);
            repchange(1,l,r,z);
        }else if(k == 2){
            scanf("%lld",&z);
            addchange(1,l,r,z);
        }else printf("%lld\n",ask(1,l,r)); 
    }
    return 0;
}

|