思路与证明

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

离线做法：

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

题目内容

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

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

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

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