← 返回题目列表

AtCoder · awc0074_c

C. 灯开关操作

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥的房间有 N 灯编号为 1 to N。最初,所有灯都关闭。

高桥将表演 M 操作。在 j第次操作 (1 \leq j \leq M),他切换所有编号在之间的灯的开关 L_j 和 R_j,包括在内。也就是说,这些灯中,亮着的灯熄灭,熄灭的灯亮着。

找出到底亮着的灯的数量 M 操作已完成。

约束

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 所有输入值均为整数

输入

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

第一行包含灯的数量 N 和操作次数 M,用空格分隔。的 j第行 (1 \leq j \leq M) 以下内容 M 行包含左端点 L_j 和右端点 要切换的间隔的 R_j 要切换的间隔 j第一个操作,以空格分隔。

输出

打印所有亮起的灯的数量 M 操作已在一行上完成。


示例输入 1

5 2
1 3
2 4

示例输出 1

2

示例输入 2

6 3
1 4
2 5
3 6

示例输出 2

4

示例输入 3

20 5
1 10
5 15
3 8
1 20
10 15

示例输出 3

13

示例输入 4

1000 6
1 500
250 750
1 1000
400 600
1 100
800 900

示例输出 4

499

示例输入 5

1 1
1 1

示例输出 5

1