题意
一个区间，你需要在其中选出一段大于 \(k\) 的区间。
使得前 \(k\) 大的 \(s_i\) 减去区间 \(c_i\) 之差最大。
问，价值最大是多少，以及哪些点可以成为被选择的价值最大的区间的前 \(k\) 大的点。
Sol
摆摆摆，颓颓颓。
注意到有决策单调性，考虑怎么证明。
显然，设 \(f_i = \max w(i, j)\)。
有：
\[w(a, c) + w(b, d) \le w(a, b) + w(c, d) \]注意到 \(c_i\) 的贡献相同。
\[w'(a, c) + w'(b, d) \le w'(a, b) + w'(c, d) \]即证：
\[w'(a, b) + w'(a + 1, b + 1) \ge w'(a, b + 1) + w'(a + 1, b) \]注意到对于新加入的 \(a + 1\)，\(b + 1\) 两个点，在左边显然可以替换掉最小值与次小值，而在右边若最小值与次小值在同一区间，会更劣。
因此我们简单证明了决策单调性。
接下来就好做了，考虑分治，用 \(l, r\) 与 \(L, R\) 分别表示左端点的区间，与右端点的区间。
每次考虑当前的 \(mid\)，暴力枚举所有右端点，找到最优右端点。
递归 \(l, mid - 1\) 与 \(L, pos\)，以及 \(mid + 1\) 与 \(pos, R\) 即可。
考虑如何快速计算当前区间的答案。
对于 \(c\) 显然是 trivial 的，不再赘述。
考虑如何求出一个区间的前 \(k\) 大 \(s_i\)。
这显然可以直接来一发可持久化线段树。
考虑更优秀的做法。
注意到其实每次移动的区间并不多，可以使用类似莫队的方式暴力移动。
为什么移动区间量是 \(O(n \log n)\) 的？
可以考虑这样一件事情，对于左端点显然移动次数为 \(n\)，对于右端点，对于每个分治区间最劣情况下会跑满，而分治区间的总量显然是 \(O(n \log n)\) 级别的。
因此，使用两个对顶堆维护插入删除，总复杂度 \(O(n \log ^ 2 n)\)。
考虑第二问，我们在分治的过程中记录下最大的价值，以及当前区间的第 \(k\) 大值。
直接使用区间求 \(min\) 线段树覆盖，单点查询即可。
总时间复杂度：\(O(n \log ^ 2 n + n \log n)\)。
标签：log,分治,mid,Trade,P9732,CEOI2023,端点,区间,考虑 From： https://www.cnblogs.com/cxqghzj/p/18119973