传送门 秀儿操作！我们每次随一个区间，考虑求出 ≥ \ge ≥ 它的区间个数 注意到左端点固定区间大小随右端点递增，于是 ≥ \ge ≥ 一个区间的是一个前缀 如果个数 ≥ k \ge k ≥k 那么可以给每一个左端点的区间钦定一个上界，否则可以钦定一个下界 这样的期望次数是 log ⁡ n \log n logn 的，相当于每次 b a n ban ban 掉一部分 于是问题变成了对