[Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?

这道题真的超级...毒瘤 + 卡常 + 耗 RP 啊...

传送门

noteskey

题解看 shadowice 大仙 的

code

如果发现自己 T 掉了，别心急，洗把脸再交一遍试试...

//by Judge

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const ll minf=-(1ll<<47);

const int M=1e5+3;

const int BL=110;

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

template<class T>inline T Max(T a,T b){return a>b?a:b;}

template<class T>inline T Min(T a,T b){return a<b?a:b;}

inline ll read(){ ll x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int CCF=-1,Z;

inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;}

inline void print(ll x,char chr='\n'){

    if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr;

} int n,m;

struct poi{ ll x,y;

	poi operator +(const poi& b){

		return (poi){x+b.x,y+b.y};

	}

}st[BL+3];

inline bool cmp(const poi& a,const poi& b,const ll& k){return k*(b.x-a.x)>=b.y-a.y;}

inline bool cmp(const poi& a,const poi& b,const poi& c){return (a.y-c.y)*(a.x-b.x)>=(a.y-b.y)*(a.x-c.x);}

inline bool cmp(const poi& a,const poi& b,const poi& c,const poi& d){return (c.y-d.y)*(a.x-b.x)>=(a.y-b.y)*(c.x-d.x);}

inline void chull(poi* st,int& tp){ int r=tp; tp=1;

	fp(i,2,r){ while(tp>1&&cmp(st[tp-1],st[tp],st[i])) --tp; st[++tp]=st[i]; }

}

struct data{ ll sum,l,r,ans;

	data operator +(data b){return (data){sum+b.sum,Max(sum+b.l,l),Max(r+b.sum,b.r),Max(r+b.l,Max(ans,b.ans))};}

}; ll asum[BL+3]; int pos[M],bj[M];

inline void insert(const poi& a){st[a.x].y=Max(st[a.x].y,a.y);}

#define ins insert

#define B BL

#define N M

struct block{ bool FLG; int siz; int p1,p2,p3,s1,s2,s3,cut;

	data val; ll add,a[BL+3]; poi pre[BL+3],suf[BL+3],ans[BL+3];

	inline int brusolv(int l,int r){ Rg ll sum=0;

		fp(i,l+1,r) sum+=a[i],ans[i]=(poi){i-l,sum};

		fp(i,l+2,r){ sum=0; poi* nw=ans+l+1;

			fp(j,i,r) sum+=a[j],nw->y=Max(nw->y,sum),++nw;

		}

		return s3=r-l,chull(ans+l,s3),s3;

	}

	inline int solv(int l,int r){

		if(r-l<cut) return 0; if(r-l<=16) return brusolv(l,r);

		int mid=(l+r)>>1,t1=solv(l,mid),t2=solv(mid,r);

		fp(i,1,r-l) st[i]=(poi){i,minf};

		fp(i,l+1,l+t1) insert(ans[i]);

		fp(i,mid+1,mid+t2) insert(ans[i]);

		ll sum=s1=0; fp(i,mid+1,r) ++s1,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1);

		sum=s2=0; fd(i,mid,l+1) ++s2,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2);

		int i=1,j=1; insert(pre[i]+suf[j]);

		for(;i^s1&&j^s2;insert(pre[i]+suf[j]))

			cmp(pre[i],pre[i+1],suf[j],suf[j+1])?++j:++i;

		if(i^s1) for(++i;i<=s1;++i) insert(pre[i]+suf[j]);

		if(j^s2) for(++j;j<=s2;++j) insert(pre[i]+suf[j]);

		chull(st,s3=r-l); fp(i,1,s3) ans[l+i]=st[i]; return s3;

	}

	inline void aju(poi* a,int& p,const int& t){

		for(;p^t;++p) if(cmp(a[p],a[p+1],-add)) break;

	}

	inline void rebuild(){ fp(i,1,siz) a[i]+=add; add=0;

		if(!FLG){ FLG=1;fp(i,1,siz)FLG=FLG&&a[i]>=0;}

		cut=ans[p3].x,solv(0,siz);

		ll sum=s1=0; fp(i,1,siz) ++s1,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1);

		sum=s2=0; fd(i,siz,1) ++s2,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2);

		aju(pre,p1=1,s1),aju(suf,p2=1,s2),aju(ans,p3=1,s3),FLG&=(p1==s1)&&(p2==s2)&&(p3==s3);

		val=(data){sum,Max(pre[p1].y,0ll),Max(suf[p2].y,0ll),Max(ans[p3].y,0ll)};

	}

	inline ll calc(const poi& a){return Max(a.x*add+a.y,0ll);}

	inline void lb_add(ll x){

		if(FLG) return add+=x,val.sum+=siz*x,val.l=val.r=val.ans=val.sum,void();

		add+=x,aju(pre,p1,s1),aju(suf,p2,s2),aju(ans,p3,s3),FLG&=(p1==s1)&&(p2==s2)&&(p3==s3);

		val=(data){val.sum+siz*x,calc(pre[p1]),calc(suf[p2]),calc(ans[p3])};

	}

	inline data calc(int l,int r){ data res=(data){0,0,0,0};

		int tp=0; fp(i,l,r) asum[++tp]=a[i]+add;

		fp(i,1,tp) res.sum+=asum[i],res.l=Max(res.l,res.sum); res.sum=0;

		fd(i,tp,1) res.sum+=asum[i],res.r=Max(res.r,res.sum); ll mi=0;

		fp(i,1,tp) asum[i]+=asum[i-1];

		fp(i,1,tp) res.ans=Max(res.ans,asum[i]-mi),mi=Min(mi,asum[i]); return res;

	}

	inline ll fstcalc(int l,int r){ int tp=0; fp(i,l,r) asum[++tp]=a[i]+add;

		fp(i,1,tp) asum[i]+=asum[i-1]; ll mi=0,ans=0;

		fp(i,1,tp) ans=Max(ans,asum[i]-mi),mi=Min(mi,asum[i]); return ans;

	}

}bl[(M/BL)+3];

int main(){ n=read(),m=read();

	for(Rg int i=0,t=1;i<n;i+=BL,++t){

		for(Rg int j=1;j<=BL&&i+j<=n;++j)

			bl[t].a[j]=read(),pos[i+j]=t,bj[i+j]=j;

		bl[t].siz=Min(n-i,BL),bl[t].rebuild();

	} Rg int t,l,r; Rg ll x;

	fp(i,1,m){ t=read(),l=read(),r=read();

		if(t&1){ x=read();

			if(pos[l]==pos[r]){

				fp(i,bj[l],bj[r])

					bl[pos[l]].a[i]+=x;

				bl[pos[l]].rebuild();

			} else{

				fp(i,bj[l],BL) bl[pos[l]].a[i]+=x;

				bl[pos[l]].rebuild();

				fp(i,pos[l]+1,pos[r]-1) bl[i].lb_add(x);

				fp(i,1,bj[r]) bl[pos[r]].a[i]+=x;

				bl[pos[r]].rebuild();

			}

		} else{

			if(pos[l]==pos[r]) print(bl[pos[l]].fstcalc(bj[l],bj[r]));

			else{ data res=bl[pos[l]].calc(bj[l],BL);

				fp(i,pos[l]+1,pos[r]-1) res=res+bl[i].val;

				res=res+bl[pos[r]].calc(1,bj[r]),print(res.ans);

			}

		}

	} return Ot(),0;

}