如图所示

#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,m,s[100010],id[100010],maxn[1000],add[1000],del[1000],len;
//s为原数组，id[x]记录x所在块，maxn[x]记录块x内最大元素的下标，add[x]和del[x]由s[i]=s[i]+i*t-(l-1)*t可得
signed main()
{
	scanf("%lld%lld",&n,&m);
	len=sqrt(n);
	for(int i=1;i<=n;i++) id[i]=(i-1)/len+1,maxn[id[i]]=(id[i]-1)*len+1;//分块，初始化maxn
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&s[i]);
		if(s[i]>s[maxn[id[i]]]) maxn[id[i]]=i;
	}
	while(m--)
	{
		int type;
		scanf("%lld",&type);
		if(type==1)
		{
			int l,r,a,b,ans=0,base=s[1]+add[1]-del[1];
			scanf("%lld%lld",&l,&r);
			a=id[l],b=id[r];
			if(a==b)
			{
				for(int i=l;i<=r;i++) ans=max(ans,s[i]+i*add[a]-del[a]-base);
				printf("%lld\n",ans);
				continue;
			}
			for(int i=l;id[i]==a;i++) ans=max(ans,s[i]+i*add[a]-del[a]-base);
			for(int i=r;id[i]==b;i--) ans=max(ans,s[i]+i*add[b]-del[b]-base);
			for(int i=a+1;i<b;i++) ans=max(ans,s[maxn[i]]+maxn[i]*add[i]-del[i]-base);
			printf("%lld\n",ans);
			continue;
		}
		if(type==2)//暴力重构a,b所在块
		{
			int a,b;
			scanf("%lld%lld",&a,&b);
			for(int i=(id[a]-1)*len+1;i<=min(id[a]*len,n);i++) s[i]=s[i]+i*add[id[i]]-del[id[i]];
			for(int i=(id[b]-1)*len+1;i<=min(id[b]*len,n);i++) s[i]=s[i]+i*add[id[i]]-del[id[i]];
			add[id[a]]=0,del[id[a]]=0,add[id[b]]=0,del[id[b]]=0;
			maxn[id[a]]=(id[a]-1)*len+1,maxn[id[b]]=(id[b]-1)*len+1;
			s[a]=s[a]^s[b];s[b]=s[a]^s[b];s[a]=s[a]^s[b];
			for(int i=(id[a]-1)*len+1;i<=min(id[a]*len,n);i++) if(s[i]>s[maxn[id[a]]]) maxn[id[a]]=i;
			for(int i=(id[b]-1)*len+1;i<=min(id[b]*len,n);i++) if(s[i]>s[maxn[id[b]]]) maxn[id[b]]=i;
			continue;
		}
		if(type==3)//暴力处理散块，处理整块时认为maxn指针只会向右移
		{
			int l,r,a,b,k;
			scanf("%lld%lld%lld",&l,&r,&k);
			a=id[l],b=id[r];
			if(a==b)
			{
				for(int i=l,base=k;i<=r;i++,base+=k) s[i]+=base;
				for(int i=l;i<=r;i++) if(s[i]+i*add[a]-del[a]>s[maxn[a]]+maxn[a]*add[a]-del[a]) maxn[a]=i;
				continue;
			}
			for(int i=l,base=k;id[i]==a;i++,base+=k) s[i]+=base;
			for(int i=l;id[i]==a;i++) if(s[i]+i*add[a]-del[a]>s[maxn[a]]+maxn[a]*add[a]-del[a]) maxn[a]=i;
			for(int i=r,base=(r-l+1)*k;id[i]==b;i--,base-=k) s[i]+=base;
			for(int i=r;id[i]==b;i--) if(s[i]+i*add[b]-del[b]>s[maxn[b]]+maxn[b]*add[b]-del[b]) maxn[b]=i;
			for(int i=a+1;i<b;i++)
			{
				add[i]+=k;
				del[i]+=(l-1)*k;
				for(int j=maxn[i];id[j]==i;j++) if(s[j]+j*add[i]-del[i]>s[maxn[i]]+maxn[i]*add[i]-del[i]) maxn[i]=j;
			}
		}
	}
}