D - Range Set Insertion Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個の集合 S _ 1,S _ 2,\ldots,S _ N があります。 はじめ、S _ 1,S _ 2,\ldots,S _ N はすべて空集合です。

これらの集合に対して、以下のような操作を Q 回行います。i 番目 (1\le i\le Q) の操作では、整数の 3 つ組 (L _ i,R _ i,X _ i) が与えられ、以下の操作を行います。

  • S _ {L _ i},S _ {L _ i+1},\ldots,S _ {R _ i} に対して、X _ i を追加する。

すべての操作を終えたあとの S _ i の要素数を、すべての i=1,2,\ldots,N に対して求めてください。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • 1\le L _ i\le R _ i\le N\ (1\le i\le Q)
  • 1\le X _ i\le Q\ (1\le i\le Q)
  • 入力はすべて整数

入力

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

N Q
L _ 1 R _ 1 X _ 1
L _ 2 R _ 2 X _ 2
\vdots
L _ Q R _ Q X _ Q

出力

Q 回の操作をすべて終えたあとの、S _ 1 の要素数,S _ 2 の要素数,\ldots,S _ N の要素数をこの順に空白を区切りとして出力せよ。

入力例 1

8 5
2 5 1
1 4 2
7 8 1
3 6 3
2 5 2

出力例 1

1 2 3 3 3 1 1 1

5 回の操作ののち、それぞれの集合は \lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace となります。 よって、それぞれの集合の要素数である 1,2,3,3,3,1,1,1 を、この順に空白を区切りとして出力してください。

入力例 2

30 20
3 22 11
8 30 10
12 14 7
2 17 4
1 19 12
7 30 15
11 23 2
14 25 17
9 12 7
10 16 7
16 18 19
1 11 14
11 15 4
1 21 6
4 8 10
23 24 11
8 27 10
1 19 12
23 23 16
13 24 12

出力例 2

3 4 5 6 6 6 7 7 8 8 9 8 8 9 9 10 9 8 7 7 7 6 7 5 3 2 2 2 2 2

Score : 400 points

Problem Statement

There are N sets S _ 1,S _ 2,\ldots,S _ N. Initially, S _ 1,S _ 2,\ldots,S _ N are all empty sets.

The following operation is performed Q times on these sets. In the i-th operation (1\le i\le Q), a triple of integers (L _ i,R _ i,X _ i) is given, and the operation below is performed.

  • Add X _ i to S _ {L _ i},S _ {L _ i+1},\ldots,S _ {R _ i}.

For every i=1,2,\ldots,N, find the number of elements of S _ i after all operations are finished.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • 1\le L _ i\le R _ i\le N\ (1\le i\le Q)
  • 1\le X _ i\le Q\ (1\le i\le Q)
  • All input values are integers.

Input

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

N Q
L _ 1 R _ 1 X _ 1
L _ 2 R _ 2 X _ 2
\vdots
L _ Q R _ Q X _ Q

Output

Output the number of elements of S _ 1, the number of elements of S _ 2,\ldots, the number of elements of S _ N after all Q operations are finished, in this order, separated by spaces.

Sample Input 1

8 5
2 5 1
1 4 2
7 8 1
3 6 3
2 5 2

Sample Output 1

1 2 3 3 3 1 1 1

After the five operations, the sets are \lbrace2\rbrace,\lbrace1,2\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace1,2,3\rbrace,\lbrace3\rbrace,\lbrace1\rbrace,\lbrace1\rbrace, respectively. Thus, output their numbers of elements, 1,2,3,3,3,1,1,1, in this order, separated by spaces.

Sample Input 2

30 20
3 22 11
8 30 10
12 14 7
2 17 4
1 19 12
7 30 15
11 23 2
14 25 17
9 12 7
10 16 7
16 18 19
1 11 14
11 15 4
1 21 6
4 8 10
23 24 11
8 27 10
1 19 12
23 23 16
13 24 12

Sample Output 2

3 4 5 6 6 6 7 7 8 8 9 8 8 9 9 10 9 8 7 7 7 6 7 5 3 2 2 2 2 2