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

这里是~~(点名被卡的)~~$O(N\sqrt{NlogN})$做法 备注:使用下面的代码的确可以AC本题，但是由于这题卡常数卡到丧心病狂，因此我并不保证这份代码可以在任意时刻AC本题(因为你谷评测姬现在不稳定性极高，人一多你的程序就变慢了……) ____________________ #### 吐槽 我们先来看一下题目 区间加区间最大子段和 ~~这不是b站上被暴力\*\*穿的题吗？看我写个暴力切了它。~~ 数据范围$N,M \leq 10^5$ ~~笑容逐渐消失~~ 于是你上网去查题解发现bzoj原题解居然是一个$O(N^{\frac{5}{3}})$的垃圾做法 据说跑的还没暴力快…… 于是你接着去翻题解，发现了这个神奇的做法 ~~其实这道题是道正宗计算几何题~~ _____________________ ### 前置芝士:凸包和凸壳 ~~不会的话出门左转luogu模板区，包教包会~~ 对了极角序的Graham Scan是做不了这道题的，请使用Jarvis水平步进法写这道题 ________________________ ### 前置芝士:闵科夫斯基和合并凸包 **觉得太长可以先看正片，等需要学习的时候回来再看** 似乎网上并没有多少讲这个东西的教程，所以我们还是详细一点讲这个东西 我们希望解决这样的问题 给定一个点集A和一个点集B,然后我们通过这样的方式生成一个点集C 点集C的生成方式为，枚举A的所有点$(X_{a},Y_{a})$和枚举B中的所有点$(X_{b},Y_{b})$,然后将点$(X_{a}+X_{b},Y_{a}+Y_{b})$加入点集C中 ~~(一个没什么用的概念是点集C被称为点集A和点集B的闵科夫斯基和)~~ 现在我希望你在$O(|A|+|B|)$的时间内求出点集C的凸包(壳) 为了实现一个相当快速的算法我们需要充分探究点集C的性质 首先我们先证明一个结论是如果一个点要在点集C的凸包上那么这个点必须是A的凸包上的一个点和B的凸包上的一个点加出来的 那么我们发现一个性质是，如果B中只有一个点$(X_{b},Y_{b})$，我们会发现C其实是点集A整体平移了$(X_{b},Y_{b})$的点集 **因此点集C可以看成是点集A按照|B|种不同方向平移形成的点集的并集** **当然也可以看成是点集B按照|A|种不同方向平移形成点集的并集** 那么我们会发现不是凸包上的点**平移**之后依然不在凸包上 所以说一个点要想是凸包上的点，它必须是两个凸包上的点加出来的，否则他就是一个不是凸包上的点平移一个方向之后的得到的点，显然不会在凸包上 因此我们可以先对A和B求一个凸包，现在的问题变成了如何求**A的凸包**和**B的凸包**这两个点集的闵科夫斯基和的凸包。 那么我们依然可以将这个点集看做凸包A以各种不同的方向平移生成的点集，或者凸包B以各种不同的方向进行平移的点集 为了方便起见我们考虑合并凸壳的情况 然后我们发现两个凸壳的闵可夫斯基和大概是长这样  _图中红色点是凸包上的点_ 然后我们发现这张图有点像一个网格图，于是我们对于图上的一个点，如果他是点i和点j加起来得到的话，我们就将它编号为(i,j),我们以这样的方式将这个点集变成一个表格 接下来我们会发现一个有趣的事实是如果点(i,j)在凸包上，且a<i,b<j则点(a,b)一定不会在凸包上，因为从图上可以很直观的看出(i,j)将(a,b)包住了 那么这其实是一个很强的剪枝条件，它告诉我们，凸包上的点在表格中必然构成一个从$(1,1)$到$(|A|,|B|)$的路径，并且每次只能向上或向右走，如上图中的红色点构成一个从(1,1)到(4,4)的路径 证明？自行反证一下即可 所以此时我们就有了一个优秀的算法了，这个算法基于双指针 我们先求出点集A的上凸壳和点集B的上凸壳 接下来我们维护两个指针$i,j$表示在网格图上走到了$(i,j)$这个点 首先先将$(1,1)$加入点集 然后计算点$(i+1,j)$与$(i,j)$的斜率和点$(i,j+1)$与点$(i,j)$间的斜率，选择斜率较大的一侧走过去并将这个点加入点集中,比如$(i+1,j)$和$(i,j)$之间的斜率更大，那么就令i++反之令j++ 如果一侧已经无路可走就一直向上或者向右走 最后为了避免多点共线的假凸包出现就对着得到的点集接着跑一个凸包好了 这样我们就愉快的求出了点集C的凸包 ~~ok你没看错这是这道题的前置芝士,纯粹寄蒜几盒~~ ~~准备好了吗，我们进入正题~~ _____________________________ ## 本题题解 我们先考虑一下如果只有单点修改和区间最大子段和该怎么做 ~~动态dp，猫老师讲过的，转移写成矩阵之后线段树维护矩阵连乘积即可~~ 然而别忘了，早在猫老师把dp的转移写成矩阵之前就有区间最大子段和单点修改这道题了…… 这道题是有一个老式做法的 线段树上每个节点记录4个值$sum,l,r,ans$分别为区间和，区间最大后缀和，区间最大前缀和，区间最大子段和 此时我们就可以合并两个区间了，转移方程可以在网上抄/看我代码/自己手推，此处不再赘述 那么我们仔细想想，$sum,l,r,ans$这4个值完美描述了这个区间的所有信息，换句话说我们如果以某种奇技淫巧得知了这个区间的$sum,l,r,ans$的话我们就可以根本不用管这个区间到底长什么样了 所以我们对整个序列分块 现在我们需要滋磁的操作是一个整块加上一个值之后依然可以快速得知这个块的$sum,l,r,ans$ 首先最好解决的当然是sum了，随便维护一下即可 接下来比较困难的是$l,r$不过这两个是同一难度，能维护其中一个就可以维护另一个 所以我们以维护最大前缀和为例讲解一下，最大后缀和的方式就请诸位自己yy了 那么假设现在我们整块被打了一个+k标记的话我们会发现我们的目标其实是最大化这样一个函数的值 $$b=sum_{x}+kx$$ 显然是斜率优化问题，我们将$(i,sum_{i})$看成一个点，现在我们的问题变成了将一条斜率为k的直线代进这些点，要求最大化截距 当然是求出这个点集的凸包然后在这个凸包上二分一下直线和凸包的切点即可了，然后切点就是使得截距最大的点了，证明的话就是由于凸包中的所有点都在直线的一侧，自然是在直线上的点代进去之后截距最大。 所以后缀和也是同理的维护了 此时我们重构一个块的复杂度还是$O(n)$的 接下来是关键部分，如何在整块加k的情况下快速的求出ans 那么我们尝试一下仿照上边的套路，将ans写成斜率优化的形式 然后我们列出来的式子是最大化 $$kx+ans_{x}$$ 其中$ans_{x}$长度为x的最大连续子段和 但是问题来了这里我明确的告诉你ans数组只能$O(n^2)$求出 ~~笑容逐渐凝固~~ 此时如果你略微机智一点，取块长为$O(N^{\frac{1}{3}})$你将会得到一个$O(N^{\frac{5}{3}})$的过不去算法 好了我们发现直接求ans数组显然是要T飞的，但是我们仔细想一想，真的需要ans数组吗？ 可能不需要，我们需要的是$(x,ans_{x})$这个点集的凸包 ~~搞什么飞机不求数组就想求凸包？~~ ~~抱歉求凸包的快速算法是存在的~~ 具体来讲这样做，我们对整个序列进行分治，假设我们现在需要求出$(l,r)$这个区间对应的凸包 那么其实这个凸包是$(l,mid)$所有子段的凸包和$(mid,r)$所有子段的凸包，以及跨越mid的子段所形成的凸包三者归并得到的 $(l,mid)$和$(mid,r)$所对应的凸包是可以递(甩)归(锅)的 问题来了怎么求跨越mid的子段所形成的凸包？ 当然是不能求跨越mid的子段所对应的ans数组的(即ans_{x}表示，长度为x且跨越mid的最大子段和) 此时我们可以略微放低一下标准，将每一个跨越mid的区间映射成一个点$(x,y)$ (其中x表示区间长度，y表示这个区间的和)，这些点构成一个点集C,当然你的点集有$O(n^2)$个点，不过这个点集C的凸包和原来要求的凸包是相同的。 但是呢，让我们考虑一下这个点集C的生成方式 设有一个点集A$(x,suf_{x})$其中$suf$为区间$(l,mid)$的后缀和数组 设有一个点集B$(x,pre_{x})$其中$pre$为区间$(mid,r)$的前缀和数组 那么点集C的生成方式就是"枚举点集A中的每一个点$(X_{a},Y_{a})$，枚举点集B中的每一个点$(X_{b},Y_{b})$，将$(X_{a}+X_{b},Y_{a}+Y_{b})$加入点集C中。”这样的生成方式 如果觉得不是很明了的话可以这样想，枚举A中的点相当于枚举左端点，枚举B中的点相当于枚举右端点，这样就枚举全了跨越mid的所有区间，也就生成了点集C 等等，点集C的生成方式似乎有点眼熟……？ ~~点集A和点集B的闵可夫斯基和啊，不懂自己去看前置芝士~~ 所以直接求出A和B的凸包大力$O(n)$归并即可求出点集C的凸包 最后和$(l,mid)$以及$(mid,r)$的凸包归并一下就可以求出(l,r)的凸包了 算法复杂度$T(n)=2T(n/2)+O(n)=O(nlogn)$ 好的于是我们通过某些奇技淫巧搞定了重构部分的复杂度，将它控制在了$O(nlogn)$ 的级别 于是我们接下来就可以滋磁给整个块加+k的操作了~ 然后每次询问找出这些块的$sum,l,r,ans$然后挨个合并就行了 于是你信心满满的写了这个算法，交上去一看全T只剩6分 此时的算法复杂度是$O(NlogN\sqrt{N})$ 没关系，加上如下剪枝即可通过本题 _________________________ # 剪枝们 ### 优化0 开启O3,Ofast _谨慎使用其他的优化指令，极易产生负优化_ _ IO量较小快读可能不太好使_ ### 优化1 每次修改add标记的时候不在凸包上二分，而是维护一个当前的最优决策点p,由于区间加的都是正数，所以决策点只会向右移动，暴力的向右爬一下即可 这样的话打标记复杂度降至均摊$O(1)$可以将复杂度重新平衡至$O(N\sqrt{NlogN})$ ### 优化2 整个块维护一个$flag$标记表示这个块的$l,r,ans$最优决策点是否都已经爬到最右边，如果是的话那么重构时无需重新分治而是直接求一遍区间和即可，同理打标记的时候也没必要向右爬而是直接强行给l,r,ans加上一个块长乘k即可 这样的剪枝效果还是比较明显的 ### 优化3 在分治的过程中如果当前区间长度小于$14$那么直接换用$O(n^2)$暴力求出这个区间的凸包 尽管简单粗暴但是卡常效果拔群 ### 优化4 将块长设为110 _其实这个优化的意思是优化3和优化4必须联合使用，也就是说，你的递归树最多递归三层，比如说110的块长会被分治成13 14 14 14 13 14 14 14这8个区间，恰好递归3层，递归4层及更多的递归树会导致低效的代码,这里特地提到块长是因为可能根据你的常数不同会出现不同的块长，但是请务必根据你的块长调整优化3中的阈值，使得恰好递归3层_ ### 优化5 询问的区间落到同一个块中的时候直接暴力求出ans，无需求l和r 看起来然并卵的剪枝，~~不过我的代码最慢的点跑了1488ms~~所以这个优化是给卡脖子的人用的 ### 优化6 俗话说的好，最后的剪枝剪的最狠 由于每次区间加的都是正数，所以我们观察到每次区间加的时候最大子段和的长度只会单调增加而不会减少，这个性质即使是块的一部分被加了也成立 因此我们重构的时候可以记录一下重构前ans最优决策点的x，也就是之间最大子段和的长度，分治的时候**如果当前区间长度小于x就直接跳出** 如果rp好一点的话通常一半的递归树就被你砍掉了 但是这个剪枝也有完全失效的时候，就是这个块是一堆非常大的负值，此时你的最大子段和长度一直是0等于没剪枝 不过这也意味这你的最优决策点无法向右爬，所以这种数据本身跑的就不是特别慢 ### 优化7 ~~现在luogu评测姬速度忽高忽低，如果觉得自己代码海星，交之间洗洗脸，没准能过~~ __________________________________ 我写了117行，相信应该不算特别长 好了上代码~ ```C #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;const int B=110;typedef long long ll;int n;int m;const ll minf=-(1LL<<47);//点结构体，叉积计算 struct poi{ll x;ll y;friend poi operator +(poi a,poi b){return (poi){a.x+b.x,a.y+b.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 ll& k){return k*(b.x-a.x)>=b.y-a.y;} 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)//jarvis水平步进法求凸包 {int i,r;for(i=2,r=tp,tp=1;i<=r;i++){while(tp>1&&cmp(st[tp-1],st[tp],st[i]))tp--;st[++tp]=st[i];}} struct data//最大子段和的结构体 { ll sum;ll l;ll r;ll ans; friend data operator +(data a,data b) {return (data){a.sum+b.sum,max(a.sum+b.l,a.l),max(a.r+b.sum,b.r),max(a.r+b.l,max(a.ans,b.ans))};} };poi st[B+10];ll asum[B+10]; inline void ins(const poi& a){st[a.x].y=max(st[a.x].y,a.y);} struct block { data val;int siz;poi pre[B+10];poi suf[B+10];poi ans[B+10];ll a[B+10];ll add;bool FLG; int p1;int p2;int p3;int s1;int s2;int s3;int cut; inline int brusolve(int l,int r)//暴力代码 { ll sum=0;for(int i=l+1;i<=r;i++)sum+=a[i],ans[i]=(poi){i-l,sum}; for(int i=l+2;i<=r;i++) {sum=0;poi* nw=ans+l+1;for(int j=i;j<=r;j++,++nw)sum+=a[j],nw->y=max(nw->y,sum);} s3=r-l;chull(ans+l,s3);return s3; } inline int solve(int l,int r)//暴力剪枝和单调性剪枝 { if(r-l<cut)return 0;if(r-l<=16){return brusolve(l,r);} int mid=(l+r)/2;int t1=solve(l,mid);int t2=solve(mid,r); for(int i=1;i<=r-l;i++)st[i]=(poi){i,minf};//插入左右两边的凸包 for(int i=l+1;i<=l+t1;i++)ins(ans[i]);for(int i=mid+1;i<=mid+t2;i++)ins(ans[i]); ll sum=0;s1=0;for(int i=mid+1;i<=r;i++)s1++,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1); sum=0;s2=0;for(int i=mid;i>l;i--)s2++,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2); int i=1;int j=1;ins(pre[i]+suf[j]);//闵可夫斯基和合并凸包 while(i!=s1&&j!=s2) {(cmp(pre[i],pre[i+1],suf[j],suf[j+1])?j:i)++;ins(pre[i]+suf[j]);} if(i!=s1)for(i++;i<=s1;i++)ins(pre[i]+suf[j]); if(j!=s2)for(j++;j<=s2;j++)ins(pre[i]+suf[j]); chull(st,s3=r-l);for(int i=1;i<=s3;i++)ans[l+i]=st[i];return s3; }//暴力向右爬的函数 inline void aju(poi* a,int& p,const int& t){while(p!=t)if(cmp(a[p],a[p+1],-add))break;else p++;} inline void rebuild() { for(int i=1;i<=siz;i++)a[i]+=add;add=0;//判一下是否全部爬到底 if(FLG==false){FLG=true;for(int i=1;i<=siz;i++)FLG=FLG&&(a[i]>=0);} if(FLG){val.sum=0;for(int i=1;i<=siz;i++)val.sum+=a[i];val.l=val.r=val.ans=val.sum;return;} cut=ans[p3].x;solve(0,siz); ll sum=0;s1=0;for(int i=1;i<=siz;i++)s1++,sum+=a[i],pre[s1]=(poi){s1,sum};chull(pre,s1); sum=0;s2=0;for(int i=siz;i>=1;i--)s2++,sum+=a[i],suf[s2]=(poi){s2,sum};chull(suf,s2); p1=1;aju(pre,p1,s1);p2=1;aju(suf,p2,s2);p3=1;aju(ans,p3,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){add+=x;val.sum+=siz*x;val.l=val.r=val.ans=val.sum;return;} 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 ret=(data){0,0,0,0}; int tp=0;for(int i=l;i<=r;i++)asum[++tp]=a[i]+add; for(int i=1;i<=tp;i++)ret.sum+=asum[i],ret.l=max(ret.l,ret.sum);ret.sum=0; for(int i=tp;i>=1;i--)ret.sum+=asum[i],ret.r=max(ret.r,ret.sum);ll mi=0; for(int i=1;i<=tp;i++)asum[i]+=asum[i-1]; for(int i=1;i<=tp;i++)ret.ans=max(ret.ans,asum[i]-mi),mi=min(mi,asum[i]); return ret; } inline ll fstcalc(int l,int r)//如果是同一个块直接暴力就行了 { int tp=0;for(int i=l;i<=r;i++)asum[++tp]=a[i]+add; for(int i=1;i<=tp;i++)asum[i]+=asum[i-1];ll mi=0;ll ans=0; for(int i=1;i<=tp;i++)ans=max(ans,asum[i]-mi),mi=min(mi,asum[i]);return ans; } }bl[(N/B)+10];int bi[N];int bj[N]; int main() { scanf("%d%d",&n,&m);//分块的一般操作 for(int i=0,t=1;i<n;i+=B,t++) { for(int j=1;j<=B&&i+j<=n;j++)scanf("%lld",&bl[t].a[j]),bi[i+j]=t,bj[i+j]=j; bl[t].siz=min(n-i,B);bl[t].rebuild(); } for(int i=1;i<=m;i++) { int t;int l;int r;ll x;scanf("%d%d%d",&t,&l,&r); if(t==1) { scanf("%lld",&x); if(bi[l]==bi[r]){for(int i=bj[l];i<=bj[r];i++)bl[bi[l]].a[i]+=x;bl[bi[l]].rebuild();} else { for(int i=bj[l];i<=B;i++)bl[bi[l]].a[i]+=x;bl[bi[l]].rebuild(); for(int i=bi[l]+1;i<bi[r];i++)bl[i].lb_add(x); for(int i=1;i<=bj[r];i++)bl[bi[r]].a[i]+=x;bl[bi[r]].rebuild(); } } else { if(bi[l]==bi[r]){printf("%lld\n",bl[bi[l]].fstcalc(bj[l],bj[r]));} else { data ret=bl[bi[l]].calc(bj[l],B); for(int i=bi[l]+1;i<bi[r];i++)ret=ret+bl[i].val; ret=ret+bl[bi[r]].calc(1,bj[r]);printf("%lld\n",ret.ans); } } }return 0; } ```