考前加人品

费用提前计算看别的题解。

如果是用斜率优化，

$f_j = (st{_i} + S) * sc{_j} + (f{_i} - sc{_i} * st{_i} - sc{_n} * S)$

二分凸包看别的题解。

但是我们有更简单的做法，使用李超线段树。

我们可以动态在一个平面加入直线维护最小值，

将$x$坐标看成$i$相关量，注意这里与斜率正好相反，这是因为斜率维护的是相邻两个决策点的量的关系，所以我们的$y$和$x$都应该确定，而李超是直接维护一个量的所有情况，所以是$k$和$b$确定，显然后者限制更少。

线段树代码如下：

#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;

const int N = 3e5 + 10, INF=1e18;
int n, S;
int st[N], sc[N], f[N], pos[N], s[N<<2];
vector<int> tmp;
struct Ed{
    int k,b;
}li[N];
inline void mk(int p){
    li[p].k=-sc[p],li[p].b=f[p]+S*(sc[n]-sc[p]);
}
#define Y(i,x) (li[i].b+li[i].k*x)
void update(int p,int l,int r,int x){
    int mid=l+r>>1;
    if(Y(x,tmp[mid])<Y(s[p],tmp[mid])) swap(x,s[p]);
    if(l==r) return;
    if(Y(x,tmp[l])<Y(s[p],tmp[l])) update(ls,l,mid,x);
    if(Y(x,tmp[r])<Y(s[p],tmp[r])) update(rs,mid+1,r,x);
}
int query(int p,int l,int r, int x){
    if(l==r) return Y(s[p],tmp[l]);
    int mid=l+r>>1;
    int v=Y(s[p],tmp[x]);
    if(tmp[x]<=tmp[mid]) v=min(v,query(ls,l,mid,x));
    else v=min(v,query(rs,mid+1,r,x));
    return v;
}
signed main()
{
    scanf("%lld%lld", &n, &S);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &st[i], &sc[i]);
        st[i] += st[i-1], sc[i] += sc[i-1];
        tmp.push_back(st[i]);
    }
    tmp.push_back(-INF);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(int i=1;i<=n;i++) pos[i]=lower_bound(tmp.begin(),tmp.end(),st[i])-tmp.begin();
    int tn=tmp.size()-1;
    li[0].b=INF;
    f[1]=st[1]*sc[1]+S*sc[n];mk(1);
    update(1,1,tn,1);
    for(int i=2;i<=n;i++){
        f[i]=st[i]*sc[i]+S*sc[n];
        f[i]=min(f[i],query(1,1,tn,pos[i])+st[i]*sc[i]);
        mk(i);update(1,1,tn,i);
    }
    printf("%lld", f[n]);
    return 0;
}

然后显然的，Y(a,b)中a是下标，b是值，所以离散化的数组要带上（离散化是因为李超和值域相关），广义李超树还可以维护反比例函数，略去不讲。