C - Light Switch Operation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君の部屋には、1 から N までの番号がついた 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

1 行目には、照明の個数 N と操作の回数 M がスペース区切りで与えられます。続く M 行のうち j 行目 (1 \leq j \leq M) には、j 回目の操作で切り替える区間の左端 L_j と右端 R_j がスペース区切りで与えられます。

出力

M 回の操作をすべて終えた後に点灯している照明の個数を、1 行で出力してください。

入力例 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

Score : 366 pts

Problem Statement

Takahashi's room has N lights numbered from 1 to N. Initially, all lights are turned off.

Takahashi will perform M operations. In the j-th operation (1 \leq j \leq M), he toggles the switches of all lights whose numbers are between L_j and R_j, inclusive. That is, among those lights, the ones that are on are turned off, and the ones that are off are turned on.

Find the number of lights that are on after all M operations have been completed.

Constraints

  • 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)
  • All input values are integers

Input

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

The first line contains the number of lights N and the number of operations M, separated by a space. The j-th line (1 \leq j \leq M) of the following M lines contains the left endpoint L_j and the right endpoint R_j of the interval to be toggled in the j-th operation, separated by a space.

Output

Print the number of lights that are on after all M operations have been completed, on a single line.

Sample Input 1

5 2
1 3
2 4

Sample Output 1

2

Sample Input 2

6 3
1 4
2 5
3 6

Sample Output 2

4

Sample Input 3

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

Sample Output 3

13

Sample Input 4

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

Sample Output 4

499

Sample Input 5

1 1
1 1

Sample Output 5

1