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

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: styx

题目描述

题目译自 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 行,每行包括一个数字,为送来的套娃经过若干次嵌套后,没有被套的套娃数量最小的个数。

样例

样例输入 1

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

样例输出 1

0
1
2

样例解释 1

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

样例输入 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

样例输出 2

3
1
3
5
0
2
1
3

数据范围与提示

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

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

Subtask 限制 分数
1 N\le 10,Q=1 11
2 N\le 100,Q=1 15
3 N,Q\le 2000 25
4 无追加限制 49