original link - https://nanti.jisuanke.com/t/41306

题意：

给出$n$n个人的到来时间$t_i$ti​和手洗的时间为$y$y。

每个人可以手洗或者机洗，一个时间内只能有一个人机洗，对于每种机洗时间$x\in[1,y]$x∈[1,y]，求最短完成时间。

解析：

假设答案中$i$i要手洗，那么显然之前的人也要手洗（不可能使答案变劣）。

那么设第$i$i人最后手洗，答案应该是$max(t_i+y,max_{j>i}(t_j+(n-j+1)x))$max(ti​+y,maxj>i​(tj​+(n−j+1)x))

后面部分也不是很难懂，设$p$p为之后全部连续至结束的那个人。如果$p$p之前有空挡，那么答案一定不会是$t_j+(n-j+1)x\;(j&lt;p)$tj​+(n−j+1)x(j<p)，所以答案就是$t_p(n-p+1)x$tp​(n−p+1)x，也就是$max_{j&gt;i}(t_j+(n-j+1)x)$maxj>i​(tj​+(n−j+1)x)

---

考虑最后的答案，对于第$i$i个人，如果手洗$t_i+y$ti​+y，机洗$t_i+(n-i+1)x$ti​+(n−i+1)x，取一个小的即可。而如果我们以$x$x做下标建树，第$i$i个人的贡献就是一条折线。我们用李超树维护折线，对于每个$x$x取最大值即可。

这边可以单单取$t_i+(n-i+1)x$ti​+(n−i+1)x是因为如果出现不连续，实际值大于$t_i+(n-i+1)x$ti​+(n−i+1)x的话，这个状态一定会被另外一个点带来。

代码：

/*
 *  Author : Jk_Chen
 *    Date : 2019-09-06-13.16.04
 */
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair<int, int>
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<x<<'\n';
const LL mod=1e9+7;
const int maxn=1e6+9;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
/*_________________________________________________________head*/

struct line{
    bool have;
    LL k,b;
}tr[maxn<<2];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
void build(int rt,int l,int r){
    tr[rt].have=0;
    if(l==r)return;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void update(LL k,LL b,int L,int R,int rt,int l,int r){
    //printf("update %lld x + %lld, %d %d\n",k,b,L,R);
    if(!(l>=L&&r<=R)){
        if(L<=mid)update(k,b,L,R,ls,l,mid);
        if(R>mid)update(k,b,L,R,rs,mid+1,r);
        return;
    }
    if(!tr[rt].have){
        tr[rt].k=k,
        tr[rt].b=b,
        tr[rt].have=1;
        return;
    }
    LL Old=tr[rt].k*l+tr[rt].b,Old_=tr[rt].k*r+tr[rt].b;
    LL New=k*l+b,New_=k*r+b;
    if(Old>=New&&Old_>=New_)return;
    if(Old<=New&&Old_<=New_){
        tr[rt].k=k,
        tr[rt].b=b;
        return;
    }
    // k won't equiv tr[rt].k
    double pos=-(b-tr[rt].b)/(1.0*k-tr[rt].k);
    if(Old<=New){
        if(pos<=mid){
            update(k,b,L,R,ls,l,mid);
        }
        else{
            update(tr[rt].k,tr[rt].b,L,R,rs,mid+1,r);
            tr[rt].k=k,tr[rt].b=b;
        }
    }
    else{
        if(pos>=mid){
            update(k,b,L,R,rs,mid+1,r);
        }
        else{
            update(tr[rt].k,tr[rt].b,L,R,ls,l,mid);
            tr[rt].k=k,tr[rt].b=b;
        }
    }
}

LL query(int x,int rt,int l,int r){ // query most value at x
    LL ans=-2e18;
    if(tr[rt].have)
        ans=tr[rt].k*x+tr[rt].b;
    if(l==r)return ans;
    if(x<=mid)ans=max(ans,query(x,ls,l,mid));
    else ans=max(ans,query(x,rs,mid+1,r));
    return ans;
}

int t[maxn];
int main(){
    int n,y;
    while(cin>>n>>y){
    build(1,1,y);
    rep(i,1,n)
        t[i]=rd();
    sort(t+1,t+1+n);
    rep(i,1,n){
        if(y/(n-i+1)>=1)
            update(n-i+1,t[i],1,y/(n-i+1),1,1,y);
        if(y/(n-i+1)+1<=y)
            update(0,t[i]+y,y/(n-i+1)+1,y,1,1,y);
    }
    rep(i,1,y){
        printf("%lld%c",query(i,1,1,y)," \n"[i==y]);
    }}
    return 0;
}