LG#P3740. [HAOI2014] 贴海报
[HAOI2014] 贴海报
P3740 [HAOI2014] 贴海报
题目描述
Bytetown 城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的宣传墙。
张贴规则如下:
宣传墙是一个长度为 个单位的长方形,每个单位记为一个格子;
所有张贴的海报的高度必须与宣传墙的高度一致;
每张海报用两个整数 表示,即从第 个格子到第 个格子张贴海报;
后贴的海报可以覆盖之前已贴的海报,也可以只覆盖其中的一部分。
现在请你判断,张贴完所有海报后,宣传墙上还可以看见多少张海报。若一张海报至少有一个格子没有被之后张贴的海报覆盖,则这张海报是可见的。
输入格式
第一行输入两个整数 $n, m \left(10 \leqq n \leqq 10^7;\ 1 \leqq m \leqq 1000\right)$ 代表宣传墙的长度与海报的数量。
此后 行,第 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq b_i \leqq n\right)$,代表第 张海报张贴的格子区间。海报按照输入顺序依次张贴。
输入中的所有整数均为正整数,相邻整数之间用一个空格分隔。
输出格式
在一行上输出一个整数,代表张贴完所有海报后仍然可见的海报数量。
测试样例
100 5
1 4
2 6
8 10
3 4
7 10
4
样例 1 解释
宣传墙的长度为 ,共张贴 张海报,过程如下:
第 张海报覆盖格子 ;
第 张海报覆盖格子 ,覆盖了第 张海报在格子 上的部分;
第 张海报覆盖格子 ;
第 张海报覆盖格子 ,覆盖了第 张海报在格子 上的部分;
第 张海报覆盖格子 ,覆盖了第 张海报的全部格子。
最终,第 张海报的格子 、第 张海报的格子 、第 张海报的格子 、第 张海报的格子 仍然可见。第 张海报的所有格子都被第 张海报覆盖,不可见。
因此共有 张海报可见。
10 6
1 5
2 6
4 7
6 9
3 5
8 10
5
样例 2 解释
宣传墙的长度为 ,共张贴 张海报:
第 张海报覆盖格子 ,其中格子 被第 张海报覆盖,格子 被第 张海报覆盖,因此它不可见;
其余 张海报都至少有一个格子没有被之后的海报覆盖,因此它们可见。
因此共有 张海报可见。
提示
下图为样例 1 的示意图。
