2729 「JOISC 2016 Day 1」俄罗斯套娃

题目译自 JOISC 2016 Day1 T1 「マトリョーシカ人形」

你开了一家卖俄罗斯套娃的店。因此，你向厂家订购了 $N$ 个俄罗斯套娃，这些娃娃被编号为 $1$ 到 $N$，其中第 $i$ 个套娃是一个的直径为 $R_i$ 高度为 $H_i$ 的直♂柱体 。每个俄罗斯套娃都只能套高和直径严格比他小的套娃。同时只要满足条件，俄罗斯套娃可以嵌套多次。

有一天，你收到了厂家的来电，告诉你你预定的 $N$ 个娃娃不能一次性全部做完。所以第一批只会送达直径大于等于 $A$ 并且高度小于等于 $B$ 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。

由于厂家经常搞大新闻，所以他会改变 $A$ 和 $B$ 的值，总共 $Q$ 次，因此你需要对每对 $(A,B)$ 都作出回答，询问之间互不干扰。

第一行有两个整数 $N$ 和 $Q$ ，表示套娃的个数和 $(A,B)$ 的对数；
之后的 $N$ 行，每行两个数 $R_i$ 与 $H_i$ 表示第 $i$ 个数的直径和高度；
之后的 $Q$ 行，每行两个数 $A_i$ 与 $B_i$ 表示第 $i$ 个询问， $A_i$ 与 $B_i$ 的意思如上所示。

输出包括 $Q$ 行，每行包括一个数字，为送来的套娃经过若干次嵌套后，没有被套的套娃数量最小的个数。

对于第一个询问，没有直径大于等于 $10$ 且高度小于等于 $5$ 的套娃，所以是 $0$； 对于第二个询问，直径大于等于 $3$ 且高度小于等于 $5$ 的套娃有两个：第一个，第七个。第一个能套第七个，所以没被嵌套的只有第一个，答案为 $1$； 对于第三个询问，满足条件的套娃是 $1,2,3,7$。其中 $3$ 可以装 $1$，$1$ 可以装 $7$，没有被嵌套的是 $2$ 和 $3$，答案为 $2$。

对于全部的数据，$1 \leq N,Q \leq 2\times 10^5,1 \leq R_i,H_i,A_i,B_i \leq 10^9$。

具体子任务限制及得分情况如下表：