#D0331. 偷梁换柱

偷梁换柱

题目背景

频更其阵,抽其劲旅,待其自败,而后乘之。曳其轮也。

题目描述

33DAI 有一根长度为 nn 厘米的柱子。Kitten 有 mm 根无限长的梁,编号从 1m1\sim m。33DAI 准备偷这些梁来替换自己的柱。

假设柱子每一厘米都是一段,33DAI 会按照编号从小到大的顺序依次操作,会使用编号为 ii 的梁替换自己柱子的第 liril_i\sim r_i 段。

请问最终 33DAI 的柱子包含了几种不同编号的梁。

输入格式

第一行为空格隔开的两个整数 n,mn,m

接下来 mm 行,第 ii 行为空格隔开的两个整数 li,ril_i,r_i

输出格式

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

7 3
2 6
3 5
4 4
3

假设从左往右是第 11 段到第 nn 段,0 表示原始柱子,1~m 表示 m 根梁的替换部分,则替换过程如下:

0000000 -> 0111110 -> 0122210 -> 0123210

最终有三种梁出现在了柱子上。

7 5
1 7
1 5 
1 3
1 6
1 3
3

替换过程如下:

0000000 -> 1111111 -> 2222211 -> 3332211 -> 4444441 -> 5554441

最终有三种梁出现在了柱子上。

7 3
1 6
2 7
3 5
3

替换过程如下:

0000000 -> 1111110 -> 1222222 -> 1233322

最终有三种梁出现在了柱子上。

数据规模与约定

对于 100%100\% 的数据,1n,m50001 \le n,m \le 50001lirin1\le l_i\le r_i\le n

  • 子任务 1(10 分):保证替换区域没有重叠。
  • 子任务 2(20 分):保证 li=ril_i=r_i
  • 子任务 3(30 分):保证 li=1l_i=1
  • 子任务 4(40 分):没有特殊限制。