CF1476G
\(n,m \le 10^5, 5s\)
后面视 \(n, m\) 同阶。
看到数据范围和时限，就知道题目要让我们想根号做法。鉴于数字出现次数比较适合莫队，于是考虑使用带修莫队解决这个问题。
我们有一个常用的结论：“出现次数的出现次数” 只有 \(O(\sqrt n)\) 种（\(1 + 2 + \dots\)）
设 \(cnt_i\) 表示数字 \(i\) 地出现次数，\(bucket_x\) 表示 \(cnt_i = x\) 的 \(i\) 的数量。那么题意转化为找到最小的 \(dif\)，使得存在 \(l\)，\(bucket_l + bucket_{l+ 1} + \dots + bucket_{l + dif - 1} \ge k\)。
由前面那个结论，只有 \(O(\sqrt n)\) 个是有值的，直接暴力双指针即可。
但是还有个问题，如何找到这 \(O(\sqrt n)\) 个数呢？
因为带修莫队自带 \(O(n^\frac{5}{3})\) 的复杂度，不能用线段树/set之类的东西搞，必须做到 \(O(1)\)。细心一点可以发现，虽然指针移动了 \(O(n^\frac{5}{3})\)
次，但查询只有 \(O(n)\) 次，就可以想到具有平衡复杂度的分块算法。
我们按值域分块，设阈值为 \(B\)，查询时暴力扫每一块，如果这一块内的所有数都是 \(0\)（总和为 \(0\)）就跳过，否则扫这块内的每个数，暴力寻找即可。这样的时间复杂度是 \(O(\frac{n}{B} + B\sqrt\frac{n}{B})\)（根前面那个结论同理），由求导取到合适的阈值得到 \(O(n^\frac{2}{3})\)。
时间复杂度：\(O(n^\frac{3}{5})\).
此题主要就是考察对于前面提到的结论的熟悉程度，以及对分块的理解（求不为 \(0\) 的那些 \(bucket\)）。