blog。虽然糖丸了，但是卡了还是半天卡过去了。感谢出题人开 2s /kt！！
最显然的暴力是，考虑直接算每个 \(i,j,k\) 的贡献。
- \(p_{i}\le p_k\wedge p_j\le p_k\)：贡献为 \(0\)。
- \(p_{i}>p_k\wedge p_j\le p_k\)：贡献为 \(\min(a,c)\times(p_i-p_k)\)。
- \(p_{i}\le p_k\wedge p_j>p_k\)：贡献为 \(\min(b,c)\times(p_j-p_k)\)。
- \(p_i>p_k\wedge p_j>p_k\)：再分类 \(i,j\) 大小，不妨设 \(p_i<p_j\)，那么贡献为 \(\min(c(p_j-p_k),b(p_j-p_i)+c(p_i-p_k),a(p_i-p_k)+b(p_j-p_k))\)。
注意最后一种情况很难处理，因为要对 \(p\) 做比较，不利于上数据结构。考虑强行化简，记 \(u=p_j-p_k\)，\(v=p_j-p_i\)，那么 \(p_i-p_k=u-v\)，注意这里 \(u,v\ge0\)。上面式子可以写成
\[\min(cu,cu+(b-c)v,(a+b)u-av)
\]
代码一坨史，复杂度 \(O(n\log n)\)。