「yyOI R1」youyou 的篡改（Hard Ver.）

· · 题解

Solution

Hard Version

感谢 @syksykCCC 对 Easy Ver 的看法与见解，于是有了这道 Hard Ver。

%%% %%%

接下来考虑，在只能篡改一道题难度的情况下，怎样求方案数。

如果用 t 表示篡改后的难度值，用 f(t) 表示篡改难度值为 t 的总可做性，那么 f(t) 单调递增。

但 f(t) 是不是严格单调递增的呢？其实，对于当 t 小于前 1 \sim m-1 个数中 k 个较大者的最小值，f(t) 均相等，即篡改没有影响。

但是大于时，这就严格单调递增了。

那么解法好想：提前处理以上的非单调情况，然后二分 a_m 的上下界，a_m 的单调取值显然就是 [l,r] 的取值。

总时间复杂度为 O(n \log n \log V)。

感谢 @syksykCCC 对此题的帮助与支持！ %%%