P2496 [SDOI2012] 体育课

考虑使用分块。
假设有一个修改 \(l,r,t\)，那么所有在 \([l,r]\) 之间的 \(i\),祂的值会变大 \((i-l+1)\times t\)，即 \(i\times t+t-l\times t\)，这个可以拆成 \(i\times t\) 和一个常数。
在同一个块内，考虑两个点 \(x,y(x<y)\)，设这个区间的目前的修改的值为 \(t\)，如果 \(x\) 的值比 \(y\) 的值大，那么有 \(x\times t+a_x>y\times t+a_y\)，即 \(t>-\frac{a_x-a_y}{x-y}\)，如果把 \(i\) 看成一个点 \((i,a_i)\)，那么对于三个点 \(x,y,z(x<y<z)\)，如果线段 \(xy\) 的斜率大于线段 \(yz\) 的斜率，\(y\) 就是没用的，因为当 \(y\) 超过 \(x\) 时，\(z\) 已经超过 \(y\) 了，而每次修改 \(z\) 增加的值比 \(y\) 大，所以 \(y\) 是没用的。仔细看一下，发现这个东西就是个下凸壳，块内用个单调队列维护一下，散块直接暴力重构。交换的时候直接把两个块全部重构。
时间复杂度 \(\mathcal O(n\sqrt n)\)。

代码

/*
Luogu P2496 [SDOI2012] 体育课
2026-03-18
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2>inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2>inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define int long long
const int maxn=100010,len=316,maxblock=3500;
int n,m,a[maxn],tag[maxblock],add[maxblock];
deque<int>st[maxblock];
int belong(int x){return(x-1)/len;}
int block_L(int x){return len*x+1;}
int block_R(int x){return min(len*x+len,n);}
#define fi st[x].back()
#define se st[x][st[x].size()-2]
void build(int x){
    st[x].clear();
    for(int i=block_L(x);i<=block_R(x);i++){
        while(st[x].size()>=2&&(a[i]-a[fi])*(fi-se)>=(a[fi]-a[se])*(i-fi)) st[x].pop_back();
        st[x].push_back(i);
    }
    while(st[x].size()>=2&&a[st[x][0]]<=a[st[x][1]]) st[x].pop_front();
}
void add_tag(int x){
    for(int i=block_L(x);i<=block_R(x);i++) a[i]+=i*tag[x]+add[x];
    tag[x]=add[x]=0;
}
signed main(){
    read(n,m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=0;i<=belong(n);i++) build(i);
    for(int i=1;i<=m;i++){
        int op,l,r,t;
        read(op);
        if(op==1){
            read(l,r);
            int L=belong(l),R=belong(r),ans=0;
            if(L==R) for(int j=l;j<=r;j++) ans=max(ans,a[j]+j*tag[L]+add[L]);
            else{
                for(int j=l;j<=block_R(L);j++) ans=max(ans,a[j]+j*tag[L]+add[L]);
                for(int j=r;j>=block_L(R);j--) ans=max(ans,a[j]+j*tag[R]+add[R]);
                for(int j=L+1;j<R;j++){
                    int w=st[j][0];
                    ans=max(ans,a[w]+w*tag[j]+add[j]);
                }
            }
            ans-=a[1]+tag[belong(1)]+add[belong(1)];
            write(max(ans,0ll));write("\n");
        }
        if(op==2){
            read(l,r);
            int L=belong(l),R=belong(r);
            add_tag(L),add_tag(R);
            swap(a[l],a[r]);
            build(L);
            if(L!=R) build(R);
        }
        if(op==3){
            read(l,r,t);
            int L=belong(l),R=belong(r);
            if(L==R){
                add_tag(L);
                for(int j=l;j<=r;j++) a[j]+=(j-l+1)*t;
                build(L);
                continue;
            }
            add_tag(L),add_tag(R);
            for(int j=l;j<=block_R(L);j++) a[j]+=(j-l+1)*t;
            for(int j=block_L(R);j<=r;j++) a[j]+=(j-l+1)*t;
            build(L),build(R);
            for(int j=L+1;j<R;j++){
                tag[j]+=t,add[j]+=t-l*t;
                while(st[j].size()>=2&&a[st[j][0]]+st[j][0]*tag[j]<=a[st[j][1]]+st[j][1]*tag[j]) st[j].pop_front();
            }
        }
    }
    return 0;
}