CF1787I Treasure Hunt
容易发现，他的限制其实是无用的。考虑 \(l\le q\le r\) 的情况，他的贡献是 \(s_r+s_q-s_l\)，那么我们可以将 \(s_r,s_q\) 中的较小者调整为较大者，那么一定会满足 \(r\le q\) 的限制。
所以问题转化为求所有子区间的前缀最大值&最大子段和。
- 前缀最大值：单调栈求出以 \(i\) 结尾的区间的答案。
- 最大子段和：考虑我们最大子段和的贪心，他将序列划分为若干个段。对于区间 \([L,R]\)，他的左端点会断开某个段，这部分我们需要特殊处理。那么单调栈即可处理。
复杂度应该可以做到线性。