E - Cover query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 個のマスが左右一列に並んでいます。
左から i (1\leq i\leq N) 番目のマスをマス i と呼びます。
最初、すべてのマスは白く塗られています。

Q 個のクエリが与えられるので、順に処理してください。
i (1\leq i\leq Q) 個目のクエリは次のとおりです。

2 つの整数 (L_i,R_i) (1\leq L_i\leq R_i\leq N) が与えられる。
マス L_i, L_i+1, \ldots, R_i をすべて黒く塗る。
このとき、元々白く塗られていたマスは新しく黒く塗られ、元々黒く塗られていたマスはそのままとなる。
その後、（N 個のマスのうち）白く 塗られているマスの個数を求める。

制約

  • 1\leq N\leq 10^9
  • 1\leq Q\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

Q 行出力せよ。
i 行目 (1\leq i\leq Q) には、i 個目のクエリに対する答えを出力せよ。

入力例 1

10 5
3 5
8 9
5 8
2 9
6 6

出力例 1

7
5
3
2
2

最初、10 個のマスが左右一列に並んでいます。

  • 1 個目のクエリではマス 3,4,5 を黒く塗ります。操作後、白く塗られているのはマス 1,2,6,7,8,9,10 の 7 マスです。
  • 2 個目のクエリではマス 8,9 を黒く塗ります。操作後、白く塗られているのはマス 1,2,6,7,10 の 5 マスです。
  • 3 個目のクエリではマス 5,6,7,8 を黒く塗ります。操作後、白く塗られているのはマス 1,2,10 の 3 マスです。
  • 4 個目のクエリではマス 2,3,\ldots,9 を黒く塗ります。操作後、白く塗られているのはマス 1,10 の 2 マスです。
  • 5 個目のクエリではマス 6 を黒く塗ります。操作後、白く塗られているのはマス 1,10 の 2 マスです。

よって、7,5,3,2,2 をこの順に各行に出力します。

入力例 2

1000000000 1
1 500000000

出力例 2

500000000

Score : 450 points

Problem Statement

There are N cells arranged in a row from left to right.
The i-th cell from the left (1\leq i\leq N) is called cell i.
Initially, all cells are painted white.

Process Q queries in order.
The i-th query (1\leq i\leq Q) is as follows:

Two integers (L_i,R_i) (1\leq L_i\leq R_i\leq N) are given.
Paint all cells L_i, L_i+1, \ldots, R_i black.
Here, cells that were painted white are now painted black, and cells that were painted black remain as is.
After that, find the number of cells (among the N cells) that are painted white.

Constraints

  • 1\leq N\leq 10^9
  • 1\leq Q\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

Output

Output Q lines.
The i-th line (1\leq i\leq Q) should contain the answer to the i-th query.

Sample Input 1

10 5
3 5
8 9
5 8
2 9
6 6

Sample Output 1

7
5
3
2
2

Initially, 10 cells are arranged in a row from left to right.

  • The first query paints cells 3,4,5 black. After the operation, the cells painted white are cells 1,2,6,7,8,9,10, which is 7 cells.
  • The second query paints cells 8,9 black. After the operation, the cells painted white are 1,2,6,7,10, which is 5 cells.
  • The third query paints cells 5,6,7,8 black. After the operation, the cells painted white are 1,2,10, which is 3 cells.
  • The fourth query paints cells 2,3,\ldots,9 black. After the operation, the cells painted white are 1,10, which is 2 cells.
  • The fifth query paints cell 6 black. After the operation, the cells painted white are cells 1,10, which is 2 cells.

Thus, output 7,5,3,2,2 in this order on each line.

Sample Input 2

1000000000 1
1 500000000

Sample Output 2

500000000