C - Range Addition Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の整数からなる数列を管理しています。数列の要素には左から順に 1 から N までの番号が付けられており、最初はすべての要素の値が 0 です。

高橋君はこの数列に対して M 回の操作を行います。i 回目の操作では、番号が L_i 以上 R_i 以下であるすべての要素の値に 1 を加算します。

すべての操作を行った後、数列の各要素の値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 入力はすべて整数

入力

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、数列の要素数 N と操作の回数 M が、スペース区切りで与えられる。
  • 1 + i 行目 (1 \leq i \leq M) には、i 回目の操作における区間の左端 L_i と右端 R_i が、スペース区切りで与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。i 番目 (1 \leq i \leq N) の整数は、すべての操作を行った後の数列の i 番目の要素の値を表す。

入力例 1

5 3
1 3
2 5
3 4

出力例 1

1 2 3 2 1

入力例 2

10 5
1 5
3 8
6 10
1 10
4 6

出力例 2

2 2 3 4 4 4 3 3 2 2

入力例 3

20 10
1 20
3 15
5 10
7 8
1 1
20 20
2 19
10 15
12 18
6 14

出力例 3

2 2 3 3 4 5 6 6 5 6 5 6 6 6 5 3 3 3 2 2

Score : 366 pts

Problem Statement

Takahashi manages a sequence of N integers. The elements of the sequence are numbered from 1 to N from left to right, and initially all elements have a value of 0.

Takahashi performs M operations on this sequence. In the i-th operation, he adds 1 to the values of all elements whose indices are between L_i and R_i, inclusive.

After all operations have been performed, find the value of each element in the sequence.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • All inputs 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 elements in the sequence N and the number of operations M, separated by a space.
  • The (1 + i)-th line (1 \leq i \leq M) contains the left endpoint L_i and right endpoint R_i of the interval for the i-th operation, separated by a space.

Output

Print N integers separated by spaces on a single line. The i-th integer (1 \leq i \leq N) represents the value of the i-th element of the sequence after all operations have been performed.

Sample Input 1

5 3
1 3
2 5
3 4

Sample Output 1

1 2 3 2 1

Sample Input 2

10 5
1 5
3 8
6 10
1 10
4 6

Sample Output 2

2 2 3 4 4 4 3 3 2 2

Sample Input 3

20 10
1 20
3 15
5 10
7 8
1 1
20 20
2 19
10 15
12 18
6 14

Sample Output 3

2 2 3 3 4 5 6 6 5 6 5 6 6 6 5 3 3 3 2 2