Description：

一条公路，每个点有一些人，每个点的人会走到右边第一个车站坐火车，最右边已经有了一个车站，最小化建车站代价 $+$ 所有人步行距离和。

$1\le n \le 40000$

Solution：

感觉和 小P的牧场 差不多，当时就不知道为什么没有这种做法。

设 $f[i]$ 表示到 $i$ 左边都已经有车站到，且 $i$ 建了车站的最小费用，由于这题距离范围很小，所以设 $t[i]$ 表示在位置 $i$ 有多少人。设 $\begin{align}c[i]=\sum_{k=1}^it[i],s[i]=\sum_{k=1}^it[i]\times i\end{align}$ ，那么转移方程为 $f[i]=m+\min(f[j+1]+(s[j]-s[i])-i\times(c[j]-c[i]))(j >i)$ ，变一下形就是 $f[j+1]+s[j]=i\times c[j]+f[i]-i\times c[i]+s[i]-m$ ，可以斜率优化， $x=c[j],y=f[j+1]+s[j],k=i,b=f[i]-i\times c[i]+s[i]-m$ ，因为是倒序循环所以 $x$ 单调递减， $k$ 单调递减，维护下凸壳，所以可以用单调队列维护。由于 $x$ 坐标可能相等所以不能用斜率。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

typedef long long ll;

ll m;

#define MAXN 1000010

ll t[MAXN];

ll c[MAXN],s[MAXN];

int q[MAXN],head,tail;

ll f[MAXN];

ll y[MAXN];

int main()

{

	scanf("%d%lld",&n,&m);

	int pos;

	int val;

	int mx = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&pos,&val);

		t[pos] += val;

		mx = max(mx,pos);

	}

	for(ll i = 1;i <= mx;++i)

	{

		c[i] = c[i - 1] + t[i];

		s[i] = s[i - 1] + t[i] * i; 

	}

	f[mx] = m;y[mx] = s[mx];

	q[head = tail = 1] = mx;

	for(ll i = mx - 1;i >= 0;--i)

	{

		while(head < tail && (y[q[head + 1]] - y[q[head]]) < (c[q[head + 1]] - c[q[head]]) * i)++head;

		f[i] = m + f[q[head] + 1] + (s[q[head]] - s[i]) - i * (c[q[head]] - c[i]);

		y[i] = f[i + 1] + s[i];//cout << " " << q[head] << endl;cout << " : " << y[i] << endl;

		while(head < tail && (y[q[tail]] - y[q[tail - 1]]) * (c[i] - c[q[tail]]) <= (y[i] - y[q[tail]]) * (c[q[tail]] - c[q[tail - 1]]))--tail;

		q[++tail] = i;//cout << f[i] << endl;

	}

	cout << f[0] - m << endl;

	return 0;

}