问题 6302 --1.偷梁换柱

6302: 1.偷梁换柱

题目描述

【题目背景】 频更其阵,抽其劲旅,待其自败,而后乘之。曳其轮也。 33DAI 有一根长度为 $n$ 厘米的柱子。Kitten 有 $m$ 根无限长的梁,编号从 $1\sim m$。33DAI 准备偷这些梁来替换自己的柱。 假设柱子每一厘米都是一段,33DAI 会按照编号从小到大的顺序依次操作,会使用编号为 $i$ 的梁替换自己柱子的第 $l_i\sim r_i$ 段。 请问最终 33DAI 的柱子包含了几种不同编号的梁。

输入

第一行为空格隔开的两个整数 $n,m$。 接下来 $m$ 行,第 $i$ 行为空格隔开的两个整数 $l_i,r_i$。

输出

输出一个整数,即最终 33DAI 的柱子包含了几种不同编号的梁。

样例输入输出

输入#1 复制
7 3
2 6
3 5
4 4
输出#1 复制
3
输入#2 复制
7 5
1 7
1 5 
1 3
1 6
1 3
输出#2 复制
3
输入#3 复制
7 3
1 6
2 7
3 5
输出#3 复制
3

提示

【样例1解释】 假设从左往右是第 $1$ 段到第 $n$ 段,`0` 表示原始柱子,`1~m` 表示 `m` 根梁的替换部分,则替换过程如下: `0000000 -> 0111110 -> 0122210 -> 0123210` 最终有三种梁出现在了柱子上。 【样例2解释】 替换过程如下: `0000000 -> 1111111 -> 2222211 -> 3332211 -> 4444441 -> 5554441` 最终有三种梁出现在了柱子上。 【样例3解释】 替换过程如下: `0000000 -> 1111110 -> 1222222 -> 1233322` 最终有三种梁出现在了柱子上。 【数据规模与约定】 对于 $100\%$ 的数据,$1 \le n,m \le 5000$,$1\le l_i\le r_i\le n$。 - 子任务 1(10 分):保证替换区域没有重叠。 - 子任务 2(20 分):保证 $l_i=r_i$。 - 子任务 3(30 分):保证 $l_i=1$。 - 子任务 4(40 分):没有特殊限制。
序号 标题 作者 发表时间 费用 订购数 操作