斜率优化好题。
观察后猜想应该是 dp。经过思考发现如果以点为状态，在时间这一维上是存在后效性的，而如果开二维数组 $f_{i,j}$ 表示在第 $j$ 个时刻到了 $i$ 个点过不去加强版，考虑以列车为状态。
题目有两个限制，一是出发点和结束点的限制，即上一辆车的 $y$ 是下一辆车的 $x$，二是时间的限制，即上一辆车的 $q$ 要不大于下一辆车的 $p$。
对于第一条，考虑采用类似柠檬的处理方式，每一个节点开一个 vector 维护决策，转移第 $i$ 辆车的时候直接从 $x_i$ 的决策中转移。
而对于第二条，先按照 $p_i$ 排序，但是这样有可能会导致 $p_{i-1}$ 小但是 $q_{i-1}$ 非常大，后一个虽然 $p_i$ 相对变大但是 $q_i$ 可能小于前一个的 $q_{i-1}$，这样添加决策是无序的，转移的限制也没有解决。
注意到随着 $p_i$ 的增大，决策集合只变大不缩小，所以可以再按照 $q_i$ 排序，使用双指针的思想，每次转移前先把可用的决策扔进决策集合（这些决策一定在前面转移好了），这样就解决了时间的限制。
设 $f_i$ 表示坐了第 $i$ 辆车的最小烦躁值，容易得到转移方程
\[f_i=min(f_j+A\times (p_i-q_j)^2+B\times (p_i-q_j)+C)\]有包含 $i,j$ 的平方项，很像斜率优化的标准形式，拆开，移项，整理得到：
\[f_j+A\times q_j^2-B\times q_j=2Ap_iq_j+f_i-C-A\times p_i^2\]单调队列维护下凸壳即可。
注意计算斜率时可能会出现横坐标相等的情况，需要特判为 $INF$ 或 $-INF$。
代码比较烂，请见谅。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n,m,A,B,C,ans=INF,pos[2000001],oth[2000001],f[2000001],sum[2000001],head[2000001],tail[2000001];
vector<int> ve[2000001];
struct Node{int x,y,p,q,id;}a[2000001],b[2000001];
bool cmp1(Node nd1,Node nd2){return nd1.p<nd2.p;}
bool cmp2(Node nd1,Node nd2){return nd1.q<nd2.q;}
#define sqr(x) ((x)*(x))
#define Y(i) (f[oth[i]]+A*sqr(b[i].q)-B*b[i].q)
#define X(i) (2*A*b[i].q)
#define K(i,j) (X(i)==X(j)?Y(i)>Y(j)?INF:-INF:1.0*(Y(i)-Y(j))/(X(i)-X(j)))
#define dty(i,j) (Y(i)-Y(j))
#define dtx(i,j) (X(i)-X(j))
inline void mian()
{
read(n,m,A,B,C),memset(f,-1,sizeof(f)),f[0]=0,f[2000000]=inf,oth[2000000]=2000000;
for(int i=1;i<=m;++i)read(a[i].x,a[i].y,a[i].p,a[i].q),a[i].id=i,++sum[a[i].y],b[i]=a[i];
sort(a+1,a+1+m,cmp1),sort(b+1,b+1+m,cmp2);
for(int i=1;i<=n;++i)ve[i].resize(sum[i]+3),i==1?0:ve[i][head[i]=tail[i]=1]=2000000;
for(int i=1;i<=m;++i)pos[a[i].id]=i;
for(int i=1;i<=m;++i)oth[i]=pos[b[i].id];
head[1]=tail[1]=1;
for(int i=1,j=0;i<=m;++i)
{
while(j<m&&b[j+1].q<=a[i].p)
{
++j;
while(head[b[j].y]<tail[b[j].y]&&K(ve[b[j].y][tail[b[j].y]],ve[b[j].y][tail[b[j].y]-1])>K(j,ve[b[j].y][tail[b[j].y]]))--tail[b[j].y];
ve[b[j].y][++tail[b[j].y]]=j;
}
while(head[a[i].x]<tail[a[i].x]&&K(ve[a[i].x][head[a[i].x]+1],ve[a[i].x][head[a[i].x]])<=(ld)a[i].p)
++head[a[i].x];
f[i]=f[oth[ve[a[i].x][head[a[i].x]]]]+A*sqr(a[i].p-b[ve[a[i].x][head[a[i].x]]].q)+B*(a[i].p-b[ve[a[i].x][head[a[i].x]]].q)+C;
if(a[i].y==n)ans=min(ans,f[i]+a[i].q);
}
write(ans,'\n');
}