搬这题只是为了庆祝窝洛谷过审的第一篇题解awa

首先这种格式一看就是要用数据结构维护，但我们会发现由于 $a$ 数组和 $k$ 的值都是变化的，普通数据结构几乎难以维护。

遇到这种问题，我们可以尝试往分块或者根号分治上想。

顺着这个思路，考虑寻找一下答案的性质。

发现当 $k \gt \sqrt{N}$ 时，操作时间复杂度最多只有 $O(\sqrt{N})$。

那要是 $k \le \sqrt{N}$ 怎么办？

这个时候 $k$ 已经非常小了，我们可以把 $k \le \sqrt{N}$ 的每一种情况都预处理出来。

在询问时，若 $k \gt \sqrt{N}$ 时，直接暴力模拟，反之直接输出我们预处理的结果就好了。

相当于用空间换时间，二者复杂度均为 $O(N\sqrt{N})$。

根号分治的有趣运用还有很多，这道题基本上相当于模板，还有一道类似的题目 哈希冲突

可以尝试做一做，cb 大佬的题解