题目大意

定义一个数列的指数为最大的 $x$，满足至少有 $x$ 个数大于等于 $x$。

给定长度为 $n$ 的数列，进行 $q$ 次询问，每次询问区间 $[l, r]$ 的指数。

解题思路

问题转化

指数的定义实际上是经典的 h-index 问题：

• 我们需要找到最大的 $x$，使得区间内至少有 $x$ 个数 $\ge x$

关键性质

1. 单调性：如果 $x$ 满足条件，那么所有小于 $x$ 的值也满足条件
2. 值域范围：答案不会超过区间长度，且 $x \le n$

算法选择：莫队算法

由于 $n, q \le 2 \times 10^5$，我们需要 $O(n\sqrt{n})$ 的算法。

莫队算法非常适合此类区间查询问题：

• 将询问按块排序，减少指针移动次数
• 维护当前区间内每个值的出现次数
• 动态维护当前答案

调整策略：

• 当 $t - cnt[k] > k$ 时，说明 $k+1$ 也可能满足条件，尝试增大 $k$
• 当 $t < k$ 时，说明当前 $k$ 不满足条件，需要减小 $k$

复杂度分析

• 块大小：$\sqrt{n}$
• 排序：$O(q \log q)$
• 莫队处理：$O(n\sqrt{n})$
• 总复杂度：$O(n\sqrt{n})$，在 $n = 2\times 10^5$ 时可行

总结

本题通过莫队算法高效处理区间查询，利用 h-index 的单调性质动态维护答案。关键在于：

1. 发现指数的单调性，支持 $O(1)$ 调整答案
2. 使用莫队算法处理大量区间查询
3. 通过奇偶排序优化减少指针移动