思路

先将所有读者按需求值从小到大排序。若某个需求较大的读者满意，而一个需求更小的读者不满意，那么交换二人所在的组不会破坏原本满足的条件。因此，对任意询问，存在一个最优方案，使得满意读者恰好构成排序后的某个前缀。

进一步地，可以把这个前缀划分为若干连续段，每一段对应一本书。若一段的最右端是第 $i$ 位读者，则该段至少要包含 $a_i$ 位读者，才能使段内所有人满意。

做法

设 $dp_i$ 表示前 $i$ 位读者能够被完整划分成的最多合法组数，并允许实际使用一个更短的前缀。初值为 $dp_0=0$。

若 $a_i\le i$，最后一组可以取长度 $a_i$，它前面的前缀长度为 $i-a_i$，于是以 $i$ 为末端的新方案能形成 $dp_{i-a_i}+1$ 个满意组。再与 $dp_{i-1}$ 取最大值即可维护前缀最大值。

若前 $i$ 人本身能够完整分组，并形成 $g$ 个满意组，那么剩余的 $n-i$ 人可以各自单独占一本书，所以该前缀能够支持至多 $g+n-i$ 本书。

当 $a_i>i$ 时，前 $i$ 人无法只靠自身组成使第 $i$ 人满意的组，但可以从后缀补入 $a_i-i$ 人。此时这一满意前缀至多支持 $n-a_i+1$ 本书：一个组容纳被补足的满意前缀，其余读者单独成组。

据此把每个前缀能够支持的最大书本数记入数组。若某个前缀能支持 $k$ 本书，那么合并任意两个组后也能支持 $k-1$ 本书，因此对该数组做后缀最大值，就能在常数时间回答每次询问。

正确性证明

由交换论证可知，任意最优方案都可以改造成满意读者为排序前缀的方案。对该前缀中不同书的读者按需求顺序整理，可使每组成为连续段，并且每段只需检查其最大需求，也就是段的最右端。

动态规划枚举了最后一段的最短合法长度 $a_i$。更长的最后一段可以把多出的较小需求读者留在前一个前缀方案中，不会得到比前缀最大值更优的组数。因此转移得到的正是每个可完整满足前缀的最多组数。

对每个前缀计算的书本数上界都能通过让剩余读者单独成组来达到；反之，除满意组外，每本书至少消耗一位剩余读者，所以不可能超过该上界。最后，合并组不会使任何原本满意的人失去同组读者，因此可支持的书本数具有向下封闭性。后缀最大值给出的就是每个 $k$ 的最大满意前缀长度。

复杂度

排序耗时 $O(n\log n)$，动态规划、后缀处理和全部询问耗时 $O(n+q)$，空间复杂度为 $O(n)$。