题解 P5073 【[Ynoi2015]世上最幸福的女孩】
shadowice1984
2018-12-09 13:20:25
# 管理员备注：本题解当前数据下会 WA+MLE，但仍有一定价值，现保留供参考
这不就是[P4680](https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4680)的一部分吗……
估计写了4680就可以去拿双倍经验了
(ynoi中罕见的不是分块的题)
_____________
### 前置芝士：闵可夫斯基和合并凸包
不会的话可以去把P4680,P4557写了然后您就知道这东西是什么了
核心代码就三行可以去看我代码里的linetree::hull_mg这个函数
### 前置芝士:线段树
蛤？线段树都不会就敢淦ynoi题？我建议你换道题做一做
## 本题题解
那么我们发现要求区间最大子段和，那么直觉告诉我们需要线段树
而且线段树上每个节点上需要维护4个值
分别是
区间最大前缀和，区间最大后缀和，区间最大子段和，区间和
合并左右儿子自己推一下式子就行了，应该肥肠简单就推出来了
现在我们唯一的问题就是，我们已经知道了整体被加上了$mrk$，想要询问这个节点的区间最大子段和，最大前缀和，最大子段和和区间和
那显然区间和十分好做，直接$mrk$乘区间长度+一开始的区间和就能算出来了
而区间最大前缀和和区间最大后缀和的维护难度似乎是差不多了
我们将$(x,pre(x))$和$(x,suf(x))$看成二维平面上的一个点，其中$pre(x)$表示长度为x的前缀的和，$suf(x)$表示长度为x的后缀的和
那么我们现在其实就是要最大化$mrk×x+y$的值咯
如果您对斜率优化那一套理论相当熟悉的话,你会发现只需要对前缀和和后缀和分别维护一个凸包，然后在凸包上二分一下就能求出pre和suf的值了
那么让我们将精力集中到如何求出区间最大子段和上
借助维护最大前缀和和最大后缀和的经验，我们希望构造出一个二维线性规划的形式然后这样就可以凸包上二分做这题了
那么假如我们要最大化$mrk×x+ans(x)$的值，我们的$ans(x)$是什么呢
**长度恰好为x的区间最大子段和**
~~这个东西,不好意思，只能$O(n^2)$求~~
看起来我们的思路陷入了僵局？
冷静一下你会发现我们求的其实是$(x,ans(x))$对应的凸包
这个东西还是有办法求的
首先我们可以将左右两个孩子的凸包取一个max，然后现在就是需要求出跨越mid的凸包，最后把这3个东西合并到一起就求出当前节点的ans凸包了
跨越mid的凸包的话仔细观察一下就可以发现是左孩子的suf凸包和右孩子凸包的闵可夫斯基和，这个东西可以直接$O(n)$求
这样的话我们就求出来这个节点的ans凸包了，于是我们可以在这个凸包上二分一下就可以求出来当前节点的ans了
好了看起来我们似乎做完了这题？
不不不,你发现我们需要提取log个节点的信息，每次提取信息的时候都需要二分，单次询问的复杂度达到了恐怖的$O(log^2n)$是绝对过不去的
~~看起来我们又双叒叕要在ynoi题里卡log了~~，直觉告诉我们肯定是用一个均摊的算法卡掉log
怎么办呢？
我们把询问离线，然后求出回答每个询问全局被加的值是多少，设这个值为val，然后我们把所有询问按照val从小到大排序
此时我们接着去回答这些询问，你会发现我们二分的斜率将会是单调的,这意味着最优决策点单调右移,此时我们就不需要二分了而是每个凸包上维护一个指针表示当前的最优决策点然后暴力的向右爬这个指针就ok了
这样的话我们挪动指针的均摊复杂度就是$O(n)$的不会成为复杂度的瓶颈
如此这般我们就得到了一个复杂度为$O(nlogn+n+mlogn)$的算法，可以轻松的通过本题(下面的代码没有加快读照样能过这题)
顺便说一句你可能在实现的时候需要注意一些trick，比如处理每个节点上储存的凸包的时候可以把每一层的凸包分配在一起，这样会减少一些访存的压力，还有就是要注意封装~~不然这题可能会把你写死~~
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e5+10;typedef long long ll;const ll inf=-(1LL<<50);
struct poi//点的结构体
{
ll x;ll y;
friend poi operator +(poi a,poi b){return (poi){a.x+b.x,a.y+b.y};}
friend poi operator -(poi a,poi b){return (poi){a.x-b.x,a.y-b.y};}
friend bool operator <=(poi a,poi b){return a.y*b.x<=a.x*b.y;}
};ll mrk;int n;int m;
struct hull//凸包的结构体
{
poi* st;int tp;int nw;
inline poi& operator [](const int& x){return st[x];}
inline void ins(const poi& a){st[a.x].y=max(st[a.x].y,a.y);}
inline void sis(const poi& a){st[++tp]=a;}
inline void ih(int lim){for(int i=1;i<=lim;i++)st[i]=(poi){i,inf};tp=lim;}
inline void build()
{
if(tp<=2)return;int i,lim;
for(i=3,lim=tp,tp=2;i<=lim;i++)
{
if(st[i].y==inf)continue;
while(tp>1&&(st[tp]-st[tp-1])<=(st[i]-st[tp-1]))tp--;st[++tp]=st[i];
}nw=1;
}
inline ll cbst()
{while(nw!=tp&&(-mrk)*(st[nw+1].x-st[nw].x)<(st[nw+1].y-st[nw].y))nw++;return mrk*st[nw].x+st[nw].y;}
};
struct data//最大子段和的结构体
{
ll pre;ll suf;ll ans;ll sum;
friend data operator +(data a,data b)
{
return (data){max(a.pre,a.sum+b.pre),max(a.suf+b.sum,b.suf),max(max(a.ans,b.ans),a.suf+b.pre)
,a.sum+b.sum};
}
};ll a[N];
struct linetree
{
poi pre_bas[20][N<<1];poi suf_bas[20][N<<1];poi ans_bas[20][N<<1];
poi* tp_pre[20];poi* tp_suf[20];poi* tp_ans[20];//分配内存的指针
hull pre[4*N];hull suf[4*N];hull ans[4*N];ll sum[4*N];
linetree()
{
for(int i=0;i<20;i++)tp_pre[i]=pre_bas[i];for(int i=0;i<20;i++)tp_suf[i]=suf_bas[i];
for(int i=0;i<20;i++)tp_ans[i]=ans_bas[i];
}
inline void smpmg(hull& c,hull& a,hull& b,const poi& sf)//合并前缀和后缀的凸包
{for(int i=1;i<=a.tp;i++)c.sis(a[i]);for(int i=1;i<=b.tp;i++)c.sis(sf+b[i]);c.build();}
inline void hull_mg(hull& c,hull& a,hull& b)//闵可夫斯基和合并凸包
{
int i=1;int j=1;c.ins(a[i]+b[j]);
while(i!=a.tp&&j!=b.tp)(((a[i+1]-a[i])<=(b[j+1]-b[j]))?j:i)++,c.ins(a[i]+b[j]);
while(i!=a.tp)i++,c.ins(a[i]+b[j]);while(j!=b.tp)j++,c.ins(a[i]+b[j]);
}
inline void build(int p,int l,int r,int dep)//建树，就是无脑合并一下凸包就没了
{
pre[p].st=tp_pre[dep];suf[p].st=tp_suf[dep];ans[p].st=tp_ans[dep];int mid;
if(r-l==1)
{
pre[p][2]=suf[p][2]=ans[p][2]=(poi){1,a[r]};sum[p]=a[r];
pre[p][1]=suf[p][1]=ans[p][1]=(poi){0,0};pre[p].tp=suf[p].tp=ans[p].tp=2;goto ed;
}mid=(l+r)/2;build(p<<1,l,mid,dep+1);build(p<<1|1,mid,r,dep+1);sum[p]=sum[p<<1]+sum[p<<1|1];
smpmg(pre[p],pre[p<<1],pre[p<<1|1],(poi){mid-l,sum[p<<1]});
smpmg(suf[p],suf[p<<1|1],suf[p<<1],(poi){r-mid,sum[p<<1|1]});ans[p].st++;ans[p].ih(r-l);
for(int i=1;i<=ans[p<<1].tp;i++)ans[p].ins(ans[p<<1][i]);
for(int i=1;i<=ans[p<<1|1].tp;i++)ans[p].ins(ans[p<<1|1][i]);
hull_mg(ans[p],suf[p<<1],pre[p<<1|1]);ans[p].st--;ans[p][1]=(poi){0,0};ans[p].tp++;ans[p].build();
ed:pre[p].nw=suf[p].nw=ans[p].nw=1;tp_pre[dep]=pre[p].st+pre[p].tp;
tp_suf[dep]=suf[p].st+suf[p].tp;tp_ans[dep]=ans[p].st+ans[p].tp;
}
inline data qry(int p,int l,int r,int dl,int dr)//询问直接套线段树板子就行了
{
if(dl==l&&dr==r)
{data ret=(data){pre[p].cbst(),suf[p].cbst(),ans[p].cbst(),sum[p]+(r-l)*mrk};return ret;}
int mid=(l+r)/2;
if(dr<=mid)return qry(p<<1,l,mid,dl,dr);if(dl>=mid)return qry(p<<1|1,mid,r,dl,dr);
return qry(p<<1,l,mid,dl,mid)+qry(p<<1|1,mid,r,mid,dr);
}
}lt;
struct qry
{
ll mrv;int l;int r;int fr;
friend bool operator <(qry a,qry b){return a.mrv<b.mrv;}
}qr[N<<1];int tp;ll ans[N<<1];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1,typ,l,r;i<=m;i++)//离线询问
{
scanf("%d%d",&typ,&l);
if(typ==1)mrk+=l;else scanf("%d",&r),++tp,qr[tp]=(qry){mrk,l,r,tp};
}
sort(qr+1,qr+tp+1);mrk=qr[1].mrv;
for(int i=1;i<=tp;i++)qr[i].mrv-=mrk;for(int i=1;i<=n;i++)a[i]+=mrk;lt.build(1,0,n,0);
for(int i=1;i<=tp;i++)
mrk=qr[i].mrv,ans[qr[i].fr]=lt.qry(1,0,n,qr[i].l-1,qr[i].r).ans;
for(int i=1;i<=tp;i++)printf("%lld\n",ans[i]);return 0;//拜拜程序~
}
```