Submission #72552281

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,B=500;
const long long INF=1e18;
int n,q,blk;
long long a[N];
int belong[N],L[B],R[B];
long long mx[B],mn[B],add[B];
bool rev[B];

void build(){
    blk=sqrt(n);
    for(int i=1;i<=n;i++){
        belong[i]=(i-1)/blk+1;
        if(!L[belong[i]])L[belong[i]]=i;
        R[belong[i]]=i;
    }
    for(int i=1;i<=belong[n];i++){
        mx[i]=-INF,mn[i]=INF;
        for(int j=L[i];j<=R[i];j++){
            mx[i]=max(mx[i],a[j]);
            mn[i]=min(mn[i],a[j]);
        }
    }
}

void push(int b){
    // 注意：先处理翻转，再处理加法
    if(rev[b]){
        for(int i=L[b];i<=R[b];i++){
            a[i]=-a[i];
        }
        rev[b]=0;
    }
    if(add[b]){
        for(int i=L[b];i<=R[b];i++){
            a[i]+=add[b];
        }
        add[b]=0;
    }
}

void update_block(int b){
    mx[b]=-INF,mn[b]=INF;
    for(int i=L[b];i<=R[b];i++){
        mx[b]=max(mx[b],a[i]);
        mn[b]=min(mn[b],a[i]);
    }
}

void update_add(int l,int r,long long v){
    int bl=belong[l],br=belong[r];
    if(bl==br){
        push(bl);
        for(int i=l;i<=r;i++)a[i]+=v;
        update_block(bl);
    }else{
        push(bl);
        for(int i=l;i<=R[bl];i++)a[i]+=v;
        update_block(bl);
        
        for(int i=bl+1;i<br;i++){
            // 对于整块：如果有翻转标记，加法要取反
            if(rev[i]){
                add[i]-=v;
                mx[i]-=v;
                mn[i]-=v;
            }else{
                add[i]+=v;
                mx[i]+=v;
                mn[i]+=v;
            }
        }
        
        push(br);
        for(int i=L[br];i<=r;i++)a[i]+=v;
        update_block(br);
    }
}

void update_rev(int l,int r){
    int bl=belong[l],br=belong[r];
    if(bl==br){
        push(bl);
        for(int i=l;i<=r;i++)a[i]=-a[i];
        update_block(bl);
    }else{
        push(bl);
        for(int i=l;i<=R[bl];i++)a[i]=-a[i];
        update_block(bl);
        
        for(int i=bl+1;i<br;i++){
            rev[i]^=1;
            swap(mx[i],mn[i]);
            mx[i]=-mx[i];
            mn[i]=-mn[i];
        }
        
        push(br);
        for(int i=L[br];i<=r;i++)a[i]=-a[i];
        update_block(br);
    }
}

long long query_max(int l,int r){
    int bl=belong[l],br=belong[r];
    long long res=-INF;
    if(bl==br){
        push(bl);
        for(int i=l;i<=r;i++)res=max(res,a[i]);
        update_block(bl);
    }else{
        push(bl);
        for(int i=l;i<=R[bl];i++)res=max(res,a[i]);
        update_block(bl);
        
        for(int i=bl+1;i<br;i++){
            if(rev[i]){
                // 有翻转标记时，最大值是-min + add
                res=max(res,-mn[i]+add[i]);
            }else{
                res=max(res,mx[i]+add[i]);
            }
        }
        
        push(br);
        for(int i=L[br];i<=r;i++)res=max(res,a[i]);
        update_block(br);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    // 初始数组全为0
    for(int i=1;i<=n;i++)a[i]=0;
    build();
    
    while(q--){
        int t,l,r;
        long long x;
        cin>>t>>l>>r;
        if(t==1){
            cin>>x;
            update_add(l,r,x);
        }else if(t==2){
            update_rev(l,r);
        }else{
            long long ans=query_max(l,r);
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Submission Info

Judge Result