LG#P3740. [HAOI2014] 贴海报

[HAOI2014] 贴海报

P3740 [HAOI2014] 贴海报

题目描述

\hspace{15pt}Bytetown 城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的宣传墙。

\hspace{15pt}张贴规则如下:

∙ \hspace{23pt}\bullet\,宣传墙是一个长度为 nn 个单位的长方形,每个单位记为一个格子;

∙ \hspace{23pt}\bullet\,所有张贴的海报的高度必须与宣传墙的高度一致;

∙ \hspace{23pt}\bullet\,每张海报用两个整数 a,ba, b 表示,即从第 aa 个格子到第 bb 个格子张贴海报;

∙ \hspace{23pt}\bullet\,后贴的海报可以覆盖之前已贴的海报,也可以只覆盖其中的一部分。

\hspace{15pt}现在请你判断,张贴完所有海报后,宣传墙上还可以看见多少张海报。若一张海报至少有一个格子没有被之后张贴的海报覆盖,则这张海报是可见的。

输入格式

\hspace{15pt}第一行输入两个整数 $n, m \left(10 \leqq n \leqq 10^7;\ 1 \leqq m \leqq 1000\right)$ 代表宣传墙的长度与海报的数量。

\hspace{15pt}此后 mm 行,第 ii 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq b_i \leqq n\right)$,代表第 ii 张海报张贴的格子区间。海报按照输入顺序依次张贴。

\hspace{15pt}输入中的所有整数均为正整数,相邻整数之间用一个空格分隔。

输出格式

\hspace{15pt}在一行上输出一个整数,代表张贴完所有海报后仍然可见的海报数量。

测试样例

100 5
1 4
2 6
8 10
3 4
7 10
4

样例 1 解释

\hspace{15pt}宣传墙的长度为 100100,共张贴 55 张海报,过程如下:

∙ \hspace{23pt}\bullet\,第 11 张海报覆盖格子 [1,4][1, 4];

∙ \hspace{23pt}\bullet\,第 22 张海报覆盖格子 [2,6][2, 6],覆盖了第 11 张海报在格子 2∼42 \sim 4 上的部分;

∙ \hspace{23pt}\bullet\,第 33 张海报覆盖格子 [8,10][8, 10];

∙ \hspace{23pt}\bullet\,第 44 张海报覆盖格子 [3,4][3, 4],覆盖了第 22 张海报在格子 3∼43 \sim 4 上的部分;

∙ \hspace{23pt}\bullet\,第 55 张海报覆盖格子 [7,10][7, 10],覆盖了第 33 张海报的全部格子。

\hspace{15pt}最终,第 11 张海报的格子 11、第 22 张海报的格子 2,5,62, 5, 6、第 44 张海报的格子 3,43, 4、第 55 张海报的格子 7∼107 \sim 10 仍然可见。第 33 张海报的所有格子都被第 55 张海报覆盖,不可见。

\hspace{15pt}因此共有 44 张海报可见。

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

样例 2 解释

\hspace{15pt}宣传墙的长度为 1010,共张贴 66 张海报:

∙ \hspace{23pt}\bullet\,第 33 张海报覆盖格子 [4,7][4, 7],其中格子 4,54, 5 被第 55 张海报覆盖,格子 6,76, 7 被第 44 张海报覆盖,因此它不可见;

∙ \hspace{23pt}\bullet\,其余 55 张海报都至少有一个格子没有被之后的海报覆盖,因此它们可见。

\hspace{15pt}因此共有 55 张海报可见。

提示

\hspace{15pt}下图为样例 1 的示意图。