题解：P11608 [PA 2016] 雨后的蘑菇 2 / Grzyby po deszczu 2
Wuyanru
·
·
题解
莫名其妙被卡了好几天，然后莫名其妙想明白了，写篇题解。
题目链接。
题意
现在有 n 块蘑菇地，第 i 块蘑菇地初始有 b_i 个蘑菇，每天晚上一块地会长出 a_i 个蘑菇。
你每天早上可以选择一块地，并把这块地的所有蘑菇都拿走。
对每一个 1\le k\le n 求出，如果只有前 k 天早上你可以拿蘑菇，最多能拿多少。
## 题解
首先有一些比较简单的观察。
观察一：一块地不可能被采摘两次，因为如果被摘了两次，那么第一次采摘完全是可以省略掉的。
此时这一块地拿到的总蘑菇量不变，你还可以拿多出来这一天去采一块别的蘑菇地，稳赚不亏。
观察二：按照时间顺序，所有采摘的蘑菇地，$a_i$ 是递增的。
这个也很好理解，因为如果你已经确定了采集哪些蘑菇地，那么 $b$ 的贡献就是确定的，你把 $a_i$ 大的换到后面让他多长一些肯定更优。
那么这个时候就有一个 $O(n^2)$ 的暴力了。
首先将所有蘑菇地按照 $a_i$ 升序进行排序，那么一定是先拿前面的再拿后面的。
设 $dp_{i,j}$ 表示从前 $i$ 块蘑菇地里面，选出 $j$ 块地，作为前 $j$ 天采摘的目标，最多能有多少蘑菇。
转移比较简单，直接枚举第 $i$ 块蘑菇地选不选就行。
转移方程是 $dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+(j-1)a_i+b_i)$。
那么考虑怎么优化这个东西呢，不妨想一想他有没有别的性质。
考虑相邻两天，采集蘑菇地的变化。
打个表或者自己瞎猜一下，都可以发现，第 $i$ 天与第 $i+1$ 天最优方案不同的地方，一定是恰好多采集了一块蘑菇地。
而不会出现，去掉 $2$ 块蘑菇地，再添加 $3$ 块蘑菇地这种情况。
为什么呢，假设 $i+1$ 天的最优方案，少了 $k$ 个蘑菇地而新添了 $k+1$ 个蘑菇地（特殊的，如果有多个最优方案，选择 $k$ 最小的那个）：
图中的 $0$ 表示蘑菇地两天的状态相同，$+$ 表示只有后一天选中，$-$ 表示只有前一天选中。
若 $k>0$，那么一定可以找到一对 $+1$ 和 $-1$，使得他们中间只有 $0$，比如图中的绿色框内两块蘑菇地。
考虑设当前的答案为 $S_1$，将这两块地有 $+1,-1$ 变成 $0,0$ 的方案答案设为 $S_2$。
如果有 $S_2\ge S_1$，说明 $i+1$ 天这个方案不是最优的，违背了我们的假设。
这说明有 $S_1>S_2$，这同样是矛盾的。
因为如果 $+1,-1$ 这个方案更优，那么在第 $i$ 天的时候，这两块地就应该是现在 $S_1$ 这个状态了，这说明第 $i$ 天的方案又不是最优的。
这样，我们使用了反证法，证明第 $i+1$ 天恰好比第 $i$ 天多选了一块蘑菇地。
那么这个时候我们又有一个 $O(n^2)$ 做法，对于每一天，直接枚举新选的蘑菇地是哪一块，然后选择增量最大的那个加入方案。
这是一个非常好的性质，再看一下之前的 dp 转移。
如果 $dp_{i-1,j}>dp_{i-1,j-1}+(j-1)a_i+b_i$，这说明最优方案是不选 $i$ 这块蘑菇地。
否则 $dp_{i-1,j}\le dp_{i-1,j-1}+(j-1)a_i+b_i$，这说明最优方案是选择 $i$ 这块蘑菇地。
那么考虑我们刚刚的结论，可以发现一定存在一个 $k$，满足对于 $j<k$ 的部分，最优方案是不选 $i$，而对于 $j\ge k$ 的部分，最优方案是选择 $i$。
那么这个 dp 就可以直接使用平衡树维护了，每一次直接在平衡树上二分找到 $k$ 的位置，然后分左右两侧分别转移。
左边的转移是直接不变就行，右边需要整体加一个等差数列，然后中间需要额外插入一个点。
这个做法是 $O(n\log n)$ 的，显然太难写了，因为不仅需要区间加等差数列，还需要二分，你还得维护每一个子树的第一个和最后一个节点编号。
所以我们考虑一个稍微好写一点的做法，我们直接去维护相邻两项 dp 的差。
我们设 $fp_{i,j}=dp_{i-1,j}-dp_{i-1,j-1}$，其中 $j\ge 1$，我们维护 $fp_{i,j}$ 的值。
首先来考虑 $k$ 怎么找，可以发现 $k$ 是满足 $dp_{i-1,j}\le dp_{i-1,j-1}+(j-1)a_i+b_i$ 的最小的 $j$。
而这个条件等价于 $fp_{i-1,j}\le (j-1)a_i+b_i$，这个条件可以直接在平衡树上二分。
再写出 $dp_{i,j}$ 的转移式子：
$$
dp_{i,j}=\begin{cases}dp_{i-1,j}&j<k\\dp_{i-1,j-1}+(j-1)a_i+b_i&j\ge k\end{cases}
$$
那么我们就能写出 $fp_{i,j}$ 的转移式子
$$
fp_{i,j}=\begin{cases}fp_{i-1,j}&j<k\\(j-1)a_i+b_i&j=k\\fp_{i-1,j-1}+a_i&j>k\end{cases}
$$
这样我们的平衡树就只需要维护区间加，而不是区间加等差数列了，并且由于这个二分只涉及到一个值，你也不需要记每一个子树的第一个或者最后一个点了，这实在是太牛了。
时间复杂度 $O(n\log n)$。
## 代码
```c++
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
mt19937 _rand(time(0)^clock());
struct node
{
ll a,b;
}v[1000005];
int pri[1000005];
ll num[1000005];
ll tag[1000005];
int siz[1000005];
int ls[1000005];
int rs[1000005];
int n,rt,cnt;
inline void T(int p,ll y)
{
num[p]+=y;
tag[p]+=y;
}
inline void push_down(int p)
{
if(ls[p]) T(ls[p],tag[p]);
if(rs[p]) T(rs[p],tag[p]);
tag[p]=0;
}
inline void push_up(int p)
{
siz[p]=siz[ls[p]]+siz[rs[p]]+1;
}
int merge(int u,int v)
{
if(!u||!v) return u|v;
push_down(u),push_down(v);
if(pri[u]>pri[v])
{
rs[u]=merge(rs[u],v);
push_up(u);
return u;
}
else
{
ls[v]=merge(u,ls[v]);
push_up(v);
return v;
}
}
void split(int p,int &x,int &y,ll a,ll b,int bef)
{
if(!p){ x=y=0;return ;}
push_down(p);
if(num[p]<=(bef+siz[ls[p]])*a+b)
{
y=p;
split(ls[p],x,ls[y],a,b,bef);
push_up(y);
}
else
{
x=p;
split(rs[p],rs[x],y,a,b,bef+siz[ls[p]]+1);
push_up(x);
}
}
inline int New(ll v)
{
cnt++;
num[cnt]=v,tag[cnt]=0;
ls[cnt]=rs[cnt]=0;
siz[cnt]=1,pri[cnt]=_rand();
return cnt;
}
ll ans;
void output(int p)
{
if(!p) return ;
push_down(p);
output(ls[p]);
ans+=num[p];printf("%lld\n",ans);
output(rs[p]);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) v[i].a=lread(),v[i].b=lread();
sort(v+1,v+n+1,[](node a,node b){ return a.a<b.a;});
for(int i=1;i<=n;i++)
{
int x,y;
split(rt,x,y,v[i].a,v[i].b,0);
T(y,v[i].a);
rt=merge(x,merge(New(siz[x]*v[i].a+v[i].b),y));
}
output(rt);
return 0;
}
```