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

传送门

noteskey

题解看 shadowice 大仙 的

code

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

//by Judge
#pragma GCC optimize("Ofast")
#include
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;iI;--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;
templateinline T Max(T a,T b){return a>b?a:b;}
templateinline T Min(T a,T b){return a1<<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>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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！