如题。

codeforces 上放过了错误的贪心做法，同时放过了 $O(n^2)$ 的暴力做法。

同时我看到 codeforces 上所有比我跑得快的代码似乎全是贪心。我用的是 FHQ Treap（用其他平衡树常数可能会更小）跑到了 30 ms。

同时我感觉 plate_let 提供的 做法 应该是常数+时间复杂度最优的做法之一（可惜没有其他人想到），理解起来也算容易。

所以我对原题进行了小小的加强：$n=10^6$，最大时限为 1800ms。当然，某些区间加等差数列的做法我没有去卡。我写的 std 可以在开 O2 的情况下最快的点跑到 874 ms。

具体内容见题面。如果有人认为这个加强不太合理，欢迎指出。