CJBS02｜闭区间数量统计 题解

核心算法

用 lower_bound 找到第一个不小于 $L$ 的位置，用 upper_bound 找到第一个大于 $R$ 的位置，两位置之差就是答案。

思路推导

闭区间左边界要保留等于 $L$ 的元素，所以找“第一个 $\ge L$”；右边界要越过所有等于 $R$ 的元素，所以找“第一个 $>R$”。

正确性说明

设 left 是第一个 $a_i\ge L$ 的下标，right 是第一个 $a_i>R$ 的下标。由于数组有序，恰好只有半开区间 [left,right) 内的元素同时满足 $a_i\ge L$ 与 $a_i\le R$，数量为 right-left。

复杂度

• 每次询问：$O(\log n)$；
• 总时间：$O(q\log n)$；
• 额外空间：$O(1)$。

易错点

• 闭区间右端必须使用“第一个大于 $R$”，不能找第一个不小于 $R$；
• 区间内可能没有元素，答案应为 0；
• 重复值必须全部计入；
• 不要使用 $R+1$ 代替 upper_bound，因为这会引入边界溢出风险。