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

时间:2023-03-09 04:23:31
[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;
}