我不知道将去何方，但我已在路上。

P9732 [CEOI 2023] Trade

感觉很奇奇怪怪的题。

这题乍一看没什么头绪啊。

考虑记 $[l,r]$ 的贡献 $w(l,r)$，也就是前 $k$ 大 $s$ 的和，减去 $S_r-S_{l-1}$。（其中 $S_i=\sum_{j=1}^i c_j$。）

发现 $w(l,r)$ 满足四边形不等式，即对于 $a<b<c<d$ 有 $w(a, c)+w(b,d)\ge w(a,d)+w(b,c)$。

具体证明，发现中间这一段 $[b,c]$ 会被抵消掉，也可以严格推式子证明。

也就是说，对于 $r$，最大的 $w(l,r)$ 的这个 $l$ 随着 $r$ 的增加显然是单调递增的，可以考虑用分治解决第一个求答案的问题。

时间复杂度 $\mathcal{O}(n\log n) \backsim \mathcal{O}(n\log ^2 n)$。

考虑如何找出所有最优区间，即 $w(l,r)=\text{ans}$ 的区间。

注意到对于两个区间 $[a,d],[b,c]$ 如果满足 $a<b<c<d$，那么由刚刚的四边形不等式显然有 $w(a,c)+w(b,d)\ge w(a,d)+w(b,c)$，也就是说，如果 $w(a,d)$ 与 $w(b,c)$ 都是最优区间，那么 $w(a,c)$ 与 $w(b,d)$ 也是最优区间。也就是说，我们本质上只需要考虑区间 $[a,c],[b,c],[b,d]$，发现右端点此时可以做到随着左端点的增加而增加，可以双指针。

时间复杂度 $\mathcal{O}(n\log n) \backsim \mathcal{O}(n\log ^2 n)$。

感觉是四边形不等式的很妙的应用。

看到区间最优解问题又多了一种办法了