题面
思路
首先，对于这种求第 \(k\) 大的题目一般都可以考虑二分答案，那么对于 Check 就是找当前答案的排名。对于找排名，我们尝试对与每一个右端点，维护多少个做端点可以使得这个区间的平均值为 \(mid\)。形式化地，我们枚举每一个 \(i\)，并统计有多少个 \(j\) 满足 \(j < i\) 且 \(\frac{sum[i] - sum[j - 1]}{i - j + 1} = mid\)，看上去很难维护，实际上可以进行一些转化。
这样就变得好做了（其实就是 \(i, j\) 放到等号两边，一般都可以这样化式子来对其进行数据结构的维护），我们可以用 BIT 简单维护一下。
但这样是 \(log^2\) 的，不能过。
对于这种求第 \(k\) 大的题目还有一种套路，就是在 \(k\) 较小的情况下，用优先队列来维护答案，使得地 \(t\) 次取出的答案就是第 \(t\) 小的答案，然后对当前状态进行一些调整得到后面的状态。这样做的好处是可以将前 \(k\) 的值都枚举到，他的核心就枚举前 \(k\) 小。对于一个题目能否这样做，最主要的就是看这样的调整是否存在。
如果把上式的形式看作是一个一次函数，则两条函数的交点的横坐标就是这个区间的平均值，则我们要找这些函数的从左到右的第 \(k\) 个交点。由于 \(k < 1e5\)，所以考虑按上述方法枚举每一个平均值。对于一个确定的自变量，每个函数都对应了一个点，或说是一个纵坐标。那么，可以证明，下一个交点一定是此时某两个相邻的点所代表的函数的交点（因为一开始，斜率是单减的）。于是我们可以用优先队列来维护相邻直线的交点，调整就是交换两条直线的顺序并考虑新加入的相邻。
对于去重：unordered_map，但要手写一个较为高效的 hash 函数