1000ms

Difficulty: 8

所属公司 : 科大讯飞

时间 :2025年8月23日

算法与标签>树状数组

会员或题库专享

请先，开通会员或购买题库科大讯飞机考编程题库，可解锁完整内容。

购买科大讯飞机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（科大讯飞机考编程题库），可解锁完整内容。

购买题库开通会员

思路与证明

把每个细菌看成平面上的点 $(l_i,r_i)$ 。一个查询 $[l,r]$ 的条件是 $l_i\ge l$ 且 $r_i\le r$ ，等价于统计矩形 $[l,+\infty)\times(-\infty,r]$ 中的点数。这是典型的二维偏序计数。

离线做法：

将所有细菌按 $r_i$ 升序排序；将所有查询按 $r$ 升序排序。
依次处理查询的 $r$ ，把所有满足 $r_i\le r$ 的细菌“加入”数据结构。
数据结构只按 $l_i$ 这一维统计：我们想要的是“当前已加入的点里， $l_i\ge l$ 的数量”。

题目内容

小C 在实验室中培育了 $n$ 个细菌。

第 $i$ 个细菌的生命周期用一个闭区间 $[l_i,r_i]$ 表示。

现有 $m$ 次查询，每次查询给出一个时间区间 $[l,r]$ 。

对于每次查询，请计算生命周期完全位于该区间内即 $(l ≦l_i$ 且 $r_i ≦r)$ 的细菌数量。