奖励关注

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9') 
	{ 
	    if(ch=='-') 
		{
			f=-1; 
			ch=getchar(); 
		}
	}
    while(ch>='0'&&ch<='9') 
	{ 
	    x=(x<<1)+(x<<3)+(ch^48);
	    ch=getchar(); 
	}
    return x*f;
}
const int N=2e5+7,M=357;
int n,m;
int bel[N],L[M],pos[M];
ll a[N],add[M],del[M];
vector <int> st[M];
inline void push_down(int o)
{
    for(int i=L[o];i<L[o+1];i++) 
	{
		a[i]+=add[o]*i-del[o];
	}
    add[o]=del[o]=pos[o]=0; 
	st[o].clear();
}
inline ll calc(int i,int o) 
{ 
    return a[i]+add[o]*i-del[o]; 
}
inline void upd(int o)
{
    while(pos[o]<st[o].size()-1&&calc(st[o][pos[o]],o)<=calc(st[o][pos[o]+1],o)) 
	{
		pos[o]++;
	}
}
inline void build(int o)
{
    for(int i=L[o];i<L[o+1];st[o].push_back(i),i++)
    {
    	while(st[o].size()>1&& (a[i]-a[st[o][st[o].size()-1]])*(st[o][st[o].size()-1]-st[o][st[o].size()-2])>=(a[st[o][st[o].size()-1]]-a[st[o][st[o].size()-2]])*(i-st[o][st[o].size()-1])) 
		{
			st[o].pop_back();
		}
	}
    upd(o);
}
inline void query(int l,int r)
{
    int bl=bel[l-1]+1,br=bel[r+1]-1; 
	ll res=0;
    if(bl>br)
    {
        for(int i=l;i<=r;i++) 
		{
			res=max(res,calc(i,bel[i]));
		}
        printf("%lld\n",max(0ll,res-calc(1,1))); 
		return;
    }
    for(int i=l;i<L[bl];i++) 
	{
		res=max(res,calc(i,bel[i]));
	}
    for(int i=L[br+1];i<=r;i++) 
	{
		res=max(res,calc(i,bel[i]));
	}
    for(int i=bl;i<=br;i++) 
	{
		res=max(res, calc(st[i][pos[i]],i));
	}
    printf("%lld\n",max(0ll,res-calc(1,1)));
}
inline void Swap(int x,int y)
{
    push_down(bel[x]); 
	push_down(bel[y]);
    swap(a[x],a[y]);
    build(bel[x]); 
	build(bel[y]);
}
inline void change(int l,int r,int t)
{
    int bl=bel[l-1]+1,br=bel[r+1]-1;
    if(bl>br)
    {
        push_down(bel[l]); 
		push_down(bel[r]);
        for(int i=l;i<=r;i++) 
		{
			a[i]+=1ll*(i-l+1)*t;
		}
        build(bel[l]); build(bel[r]); 
		return;
    }
    if(L[bl]!=l)
    {
        for(int i=l;i<L[bl];i++) 
		{
			a[i]+=1ll*(i-l+1)*t;
		}
        push_down(bl-1); 
		build(bl-1);
    }
    if(L[br+1]-1!=r)
    {
        for(int i=L[br+1];i<=r;i++) 
		{
			a[i]+=1ll*(i-l+1)*t;
		}
        push_down(br+1); 
		build(br+1);
    }
    for(int i=bl;i<=br;i++) 
	{
		add[i]+=t,del[i]+=1ll*(l-1)*t,upd(i);
	}
}
int main()
{
    n=read(),m=read(); 
	int T=sqrt(n)+1;
    for(int i=1;i<=n;i++)
    {
        a[i]=read(); 
		bel[i]=(i-1)/T+1;
        if(bel[i]!=bel[i-1]) 
		{
			L[bel[i]]=i;
		}
    }
    bel[n+1]=bel[n]+1; 
	L[bel[n+1]]=n+1;
    for(int i=1;i<=bel[n];i++) 
	{
		build(i);
	}
    int opt,a,b;
    for(int i=1;i<=m;i++)
    {
        opt=read(); a=read(),b=read();
        if(opt==1) 
		{ 
		    query(a,b); 
			continue; 
		}
        if(opt==2) 
		{ 
		    Swap(a,b);
			 continue; 
		}
        change(a,b,read());
    }
    return 0;
}