任务安排4

类似任务安排1，这题是斜率优化，要维护点(c_i,f_i)(ci?,fi?)组成的下凸壳(c_ici?是费用前缀和，f_ifi?是把费用提前计算后的最小代价)

本题的费用和时间都可以为负，所以要动态维护下凸壳并二分查找决策点

算出一个新的f_ifi?后，若该决策点在凸壳上方，则忽略此点，否则就要删除凸壳中的一些点并插入该点

向下凸壳中插入点的例子：

容易发现，被删除的点一定是连续的，可以二分被删除点的范围(有可能不删除任何点)

决策点即为第一个与下一个点的连线的斜率不小于S+t_iS+ti?的点，其中t_iti?是时间前缀和

每个点最多会被插入11次，删除11次，总时间复杂度为\mathcal O(n\log n)O(nlogn)

维护需要二分xx坐标，而查找转移点需要二分斜率。我的做法是维护两个multiset，一个按与下一个点的连线的斜率排序，另一个按横坐标排序，并存储在斜率集合中的对应点

#include
#define fre(x) freopen(#x".in","r",stdin), freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
const int N=100010;
const ll inf=10000000000LL;
int n;
ll f[N],S,t[N],c[N];
struct P{
    int x;// 点的编号
    ll v1,v2;// v1,v2为斜率的分子和分母
};
struct p{
    int num;// 点的编号
    ll x,y;// 点的坐标,即c[i],f[i]
    set
::iterator pos;// 在set
中的对应点的迭代器
    bool operator< (const p &a)const{
        return xmultiset
s;
multiset
kk;// 横坐标相同时需要保留纵坐标最小的点，可能不能用set
bool operator< (P a,P b){
    if(a.v2*b.v2<0)return a.v1*b.v2>b.v1*a.v2;
    return a.v1*b.v2// 比较两个点的斜率
inline bool le(ll a,ll b,ll c,ll d){
    if(b*d<0)return a*d>b*c;
    return a*d// 同上，参数是y1,x1,y2,x2
inline bool leq(ll a,ll b,ll c,ll d){
    if(b*d<0)return a*d>=b*c;
    return a*d<=b*c;
}
int main(){
    fre(a);
    s.insert(P{0,inf,1});
    kk.insert(p{0,0,0,s.begin()});// 把决策点0放入集合
    scanf("%d%lld",&n,&S);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&t[i],&c[i]);
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    for(int j,i=1;i<=n;++i){
        j=s.lower_bound(P{i,S+t[i],1})->x;// 二分决策点
        f[i]=f[j]-(S+t[i])*c[j]+t[i]*c[i]+S*c[n];
        multiset
::iterator it=kk.lower_bound(p{i,c[i],f[i],s.begin()}),l,r;
        if(it!=kk.end()&&it->x==c[i]){
            if(f[i]>=it->y)continue;
            s.erase(it->pos);
            it=kk.erase(it);
        }// 去除x坐标相同的情况
        l=r=it;// 要删除的点的范围是[l,r]
        if(it!=kk.begin()){
            --l;
            while(l!=kk.begin()&&leq(f[i]-l->y,c[i]-l->x,prev(l)->pos->v1,prev(l)->pos->v2))
                --l;// 不能组成下凸壳，删除这个点
        }
        if(it!=kk.end())
            while(next(r)!=kk.end()&&leq(r->pos->v1,r->pos->v2,r->y-f[i],r->x-c[i]))
                ++r;// 不能组成下凸壳，删除这个点
        if(it!=kk.begin()&&r!=kk.end()&&le(l->pos->v1,l->pos->v2,f[i]-l->y,c[i]-l->x))continue;// i在下凸壳上方
        if(l!=r)
            for(auto ii=next(l);ii!=r;){
                s.erase(ii->pos);
                ii=kk.erase(ii);
            }
        P dk;
        if(l!=kk.end())dk=*(l->pos);
        if(l==kk.begin()&&kk.size()>1&&le(l->pos->v1,l->pos->v2,l->y-f[i],l->x-c[i])){
            s.erase(l->pos);
            kk.erase(l);// 特判插入点在最左的情况
        }else if(it!=kk.begin()){
            dk.v1=f[i]-l->y;dk.v2=c[i]-l->x;// 重新计算i左边的点的斜率
            kk.insert(p{l->num,l->x,l->y,s.insert(dk)});s.erase(l->pos);kk.erase(l);// set不能修改，需要插入然后删除
        }
        dk.x=i;
        if(r!=kk.end())dk.v1=r->y-f[i],dk.v2=r->x-c[i];
        else dk.v1=inf,dk.v2=1;
        kk.insert(p{i,c[i],f[i],s.insert(dk)});// 将i加入凸壳
    }
    printf("%lld",f[n]);
}