题解：P11805 [PA 2017] 烧饼 2

· · 题解

首先不难发现，一定有一种最优方案，使得这些人拿到烧饼的顺序就是他们来到店里的顺序。证明考虑调整，若交换顺序，要么后者无法购买前者的烧饼，要么一个人的等待时间增加 d，另一个人的等待时间减少 d，则当前方案显然不劣。

考虑设第 i 人拿到烧饼的时间为 T_i，则显然有

T_i=\max(t_i,T_{i-1}+d)

因为前者是来店时间，后者是下一块烧饼做好的时间，当前时间要同时不小于两者，取最大值最优。此时答案即为

\sum_{1\le i\le n}(T_i-t_i)=\sum_{1\le i\le n} T_i-\sum_{1\le i\le n} t_i

考虑到 \sum_{1\le i\le n} t_i 为定值，因此只考虑求解 \sum_{1\le i\le n}T_i。

这个最大值的形式让人恼火，因为它较为难求，不妨考虑分类讨论，即讨论什么时候 \max 取前者，什么时候取后者。不难发现 T_i=t_i 当且仅当

t_i\ge\max_{j<i}(t_j+(i-j)d)

证明是容易的，因为此时不管从什么时候开始连续制作烧饼，都无法让第 i 个人立刻买到，说明 \max 中只可能选择 t_i。考虑将做饼的区间对应到数轴上，可以看出我们的选择相当于是选择一个区间连续的制作饼，则我们上面找到的 t_i 应该是一个区间的左端点。我们称这样的点 i 为断点，不难发现上面的式子可以改为

\begin{aligned}t_i-id\ge t_j-jd&\Rightarrow \frac{t_i-t_j}{i-j}\ge d,&&(i<j)\end{aligned}

于是可以采用凸包维护，于是第 i 个点成为断点当且仅当 d 小于等于 [1,i] 的凸包上 i 和其前驱点之间的斜率。

那么此时对于一个 d，我们能够找出所有的断点集合 S=\{a_0=0,a_1,\cdots,a_p,a_{p+1}=n+1\}，考虑到相邻的两个断点之间的烧饼的制作时间应当是一个等差数列且首项为 t_{a_i}，公差为 d，项数为 L=a_{i+1}-a_i，则这一段的 T_i 和可以快速计算：

\frac{(t_i+t_i+(L-1)d)L}{2}=t_iL+\frac{d}{2}(L^2-L)

注意到因为 d 是已知的，所以我们只需要知道 \sum_{0\le i\le p}t_iL,\sum_{0\le i\le p}(L^2-L) 即可 O(1) 求解。

现在考虑如何对 m 个 d 求解，通过每一个点是否作为断点的单调性，我们不难想到对所有询问离线，并按照 d 从小到大排序，那么随着我们枚举，会有一些点逐渐从集合中删去，我们只需要改动它和它的前驱，则改动复杂度是 O(1) 的，每一个点最多被删掉 1 次，则总复杂度为 O(n)，采用链表实现，复杂度瓶颈在排序，总复杂度 O(n\log n)。

code

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define pil pair<int,ll>
#define fi first
#define se second

const int N=2e5+5;

int n,m,q,top;
int id[N],rk[N],d[N];
ll s1,s2;
ll t[N],_d[N],pos[N],ans[N];
pil stk[N];
struct Node{
    int pre,nxt;
}l[N];

pil operator -(pil _1,pil _2){return {_1.fi-_2.fi,_1.se-_2.se};}
ll operator *(pil _1,pil _2){return _1.fi*_2.se-_1.se*_2.fi;}
il void Insert(int i){
    pil p={i,t[i]};
    while(top&&(p-stk[top])*(p-stk[top-1])<=0)top--;
    pos[i]=upper_bound(_d+1,_d+1+m,(t[i]-stk[top].se)/(i-stk[top].fi))-_d,stk[++top]=p;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>t[i],rk[i]=i,l[i]={i-1,i+1};
    for(int i=1;i<=m;i++)cin>>d[i],_d[i]=d[i],id[i]=i;
    sort(_d+1,_d+1+m);
    for(int i=1;i<=n;i++)Insert(i);
    sort(id+1,id+1+m,[](int _1,int _2){return d[_1]<d[_2];}),sort(rk+1,rk+1+n,[](int _1,int _2){return pos[_1]<pos[_2];});
    for(int i=1,p=1;i<=m;i++){
        while(p<=n&&pos[rk[p]]==i){
            int now=rk[p++],pre=l[now].pre,nxt=l[now].nxt;
            s1+=(nxt-now)*(t[pre]-t[now]),s2+=(ll)(nxt-now)*(now-pre),l[pre].nxt=nxt,l[nxt].pre=pre;
        }
        int idx=id[i];
        ans[idx]=s1+s2*d[idx];
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}