题解

思路

对于位置 $i$，记同类型战士中排在它前面的第 $k$ 个位置为 $p_i$；若不足 $k$ 个，则令 $p_i=0$。在询问区间 $[l,r]$ 中，位置 $i$ 能被选择，当且仅当 $p_i<l$。因此答案等于 $[l,r]$ 中满足 $p_i<l$ 的位置数。

这个判定不会受其他位置是否被选择影响：每种类型在区间内最靠前的至多 $k$ 个位置恰好满足条件，其余位置都已有至少 $k$ 个同类型前驱落在区间内。

做法

按位置从左到右维护每种类型的出现位置，即可求出全部 $p_i$。建立前缀可持久化线段树，第 $i$ 个版本加入数值 $p_i$。询问时，用第 $r$ 个版本减去第 $l-1$ 个版本，统计值域 $[0,l-1]$ 内的数量。每次查询只访问对数个节点；得到答案后再用于解密下一次询问。

部分分

当 $n,q\le2000$ 时，可在每次询问中扫描区间并统计各类型出现次数，累加每种类型与 $k$ 的较小值。

当所有 $a_i\le100$ 时，可预存每种类型的有序出现位置。每次询问对至多一百种类型二分得到区间出现次数，再累加与 $k$ 的较小值。

正确性证明

固定一种类型，并按位置列出它在区间 $[l,r]$ 中的出现。前 $k$ 个出现之前，在整个序列中与它同类型且仍位于区间内的前驱少于 $k$ 个，所以相应 $p_i<l$；从第 $k+1$ 个出现开始，第 $k$ 个同类型前驱已经不小于 $l$，所以 $p_i\ge l$。故该类型被统计的数量恰为其区间出现次数与 $k$ 的较小值。对所有类型求和即为最大可选人数。可持久化线段树的版本差精确保留位置区间 $[l,r]$ 中的全部 $p_i$，值域前缀查询又精确选出 $p_i<l$ 的项，因此每次输出正确。按顺序使用正确答案解密，所有后续区间也都正确。

复杂度

预处理和建立各版本共需 $O(n\log n)$ 时间与空间；每个询问耗时 $O(\log n)$。