思路与证明
把每个细菌看成平面上的点 (li,ri)。一个查询 [l,r] 的条件是 li≥l 且 ri≤r，等价于统计矩形 [l,+∞)×(−∞,r] 中的点数。这是典型的二维偏序计数。
离线做法：
- 将所有细菌按 ri 升序排序；将所有查询按 r 升序排序。
- 依次处理查询的 r，把所有满足 ri≤r 的细菌“加入”数据结构。
- 数据结构只按 li 这一维统计：我们想要的是“当前已加入的点里，li≥l 的数量”。
P3455.第3题-小C的细菌
题目内容
小C 在实验室中培育了 n 个细菌。
第 i 个细菌的生命周期用一个闭区间 [li,ri] 表示。
现有 m 次查询，每次查询给出一个时间区间 [l,r] 。
对于每次查询，请计算生命周期完全位于该区间内即 (l≦li 且 ri≦r) 的细菌数量。
输入描述
第一行输入两个整数 n 和 m(1≦n,m≦5×105) ，分别表示细菌的数量和查询次数。
接下来 n 行，每行输入两个整数 li 和 ri(1≦li≦ri≦109) ，表示第 i 个细菌的生命周期区间。
随后 m 行，每行输入两个整数 l 和 r(1≦l≦r≦109) ，表示一次查询的时间区间。
输出描述
输出 m 行，每行输出一个整数，表示对应查询的答案。
样例1
输入
5 3
1 2
2 5
3 4
1 10
6 8
1 5
2 6
1 10
输出
3
2
5
说明
-
共有 5 个细菌，其生命周期区间分别为：
- 第 1 个：[1,2] ；
- 第 2 个：[2,5] ；
- 第 3 个：[3,4] ；
- 第 4 个：[1,10] ；
- 第 5 个：[6,8] 。
-
查询区间 [1,5] 时，有 3 个细菌(第 1、2、3 ) 的生命周期完全在该区间内，故输出 3 ；
-
查询区间 [2,6] 时，有 2 个细菌(第 2、3 )满足条件，故输出 2 ；
-
查询区间 [1,10] 时，所有 5 个细菌都满足条件，故输出 5 。
样例2
输入
4 2
1 3
2 4
3 5
4 6
2 4
3 6
输出
1
2
