E - 信号変換器の出力種類数 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は N ステップからなる信号変換器を管理しています。この変換器は 1 以上 K 以下の整数値の信号を受け取り、変換処理を施して出力します。

入力された信号は、第 1 ステップ、第 2 ステップ、\ldots、第 N ステップの順に変換処理を受けます。第 i ステップ (1 \leq i \leq N) は整数の組 (L_i, R_i, X_i) で定められ、次の処理を行います。

  • そのステップの処理開始時点での信号値を v とする。L_i \leq v \leq R_i ならば、信号値を X_i に置き換える。そうでなければ、信号値は変化しない。

各ステップの処理後の信号値が次のステップへの入力となり、第 N ステップの処理後の信号値が変換器の最終的な出力となります。入力信号値が整数 s のとき、最終的な出力信号値を F(s) と定義します。

青木君から Q 個の質問が届きます。j 番目の質問では整数 A_j, B_j が与えられます。入力信号値を A_j 以上 B_j 以下のすべての整数としたとき、出力信号値として現れる値の種類数、すなわち集合 \{F(s) \mid s \text{ は整数}, A_j \leq s \leq B_j\} の要素数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • N \times K \leq 10^7
  • N + Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq K (1 \leq i \leq N)
  • 1 \leq X_i \leq K (1 \leq i \leq N)
  • 1 \leq A_j \leq B_j \leq K (1 \leq j \leq Q)
  • 入力はすべて整数である。

入力

N K Q
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_N R_N X_N
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q
  • 1 行目には、変換ステップ数 N、信号値の取りうる範囲の上限 K、質問数 Q がスペース区切りで与えられる。
  • 続く N 行のうち i 行目には、第 i ステップを定める整数 L_i, R_i, X_i がスペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、j 番目の質問を表す整数 A_j, B_j がスペース区切りで与えられる。

出力

ans_1
ans_2
\vdots
ans_Q

Q 行出力せよ。j 行目には、j 番目の質問に対する答え、すなわち集合 \{F(s) \mid s \text{ は整数}, A_j \leq s \leq B_j\} の要素数を出力せよ。

入力例 1

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

出力例 1

1
1
1
1

入力例 2

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

出力例 2

1
1
1
1
1

入力例 3

10 20 8
1 5 12
10 15 3
3 12 18
18 20 6
6 9 14
14 14 2
2 4 19
16 19 7
7 13 1
1 1 20
1 20
1 5
6 10
11 15
16 20
3 17
8 8
14 19

出力例 3

1
1
1
1
1
1
1
1

入力例 4

20 50 12
1 10 25
11 20 5
21 30 40
31 40 15
41 50 1
5 25 33
26 45 12
1 3 50
48 50 7
7 18 22
19 32 44
33 44 9
9 9 30
30 35 2
2 8 16
16 16 41
41 49 6
6 14 28
28 38 11
11 27 35
1 50
1 10
11 20
21 30
31 40
41 50
5 45
13 37
25 25
2 49
17 33
39 50

出力例 4

1
1
1
1
1
1
1
1
1
1
1
1

入力例 5

1 1 1
1 1 1
1 1

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi manages a signal converter consisting of N steps. This converter receives an integer signal with a value between 1 and K inclusive, applies conversion processing, and produces an output.

The input signal undergoes conversion processing in order: step 1, step 2, \ldots, step N. Step i (1 \leq i \leq N) is defined by a tuple of integers (L_i, R_i, X_i) and performs the following operation:

  • Let v be the signal value at the start of this step's processing. If L_i \leq v \leq R_i, replace the signal value with X_i. Otherwise, the signal value remains unchanged.

The signal value after each step's processing becomes the input to the next step, and the signal value after step N's processing becomes the final output of the converter. When the input signal value is an integer s, we define the final output signal value as F(s).

Aoki sends Q queries. In the j-th query, integers A_j and B_j are given. When the input signal values are all integers from A_j to B_j inclusive, find the number of distinct values that appear as output signal values, that is, the number of elements in the set \{F(s) \mid s \text{ is an integer}, A_j \leq s \leq B_j\}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • N \times K \leq 10^7
  • N + Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq K (1 \leq i \leq N)
  • 1 \leq X_i \leq K (1 \leq i \leq N)
  • 1 \leq A_j \leq B_j \leq K (1 \leq j \leq Q)
  • All inputs are integers.

Input

N K Q
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_N R_N X_N
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q
  • The first line contains the number of conversion steps N, the upper bound of possible signal values K, and the number of queries Q, separated by spaces.
  • In the following N lines, the i-th line contains the integers L_i, R_i, X_i that define step i, separated by spaces.
  • In the following Q lines, the j-th line contains the integers A_j, B_j representing the j-th query, separated by spaces.

Output

ans_1
ans_2
\vdots
ans_Q

Output Q lines. The j-th line should contain the answer to the j-th query, that is, the number of elements in the set \{F(s) \mid s \text{ is an integer}, A_j \leq s \leq B_j\}.

Sample Input 1

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

Sample Output 1

1
1
1
1

Sample Input 2

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

Sample Output 2

1
1
1
1
1

Sample Input 3

10 20 8
1 5 12
10 15 3
3 12 18
18 20 6
6 9 14
14 14 2
2 4 19
16 19 7
7 13 1
1 1 20
1 20
1 5
6 10
11 15
16 20
3 17
8 8
14 19

Sample Output 3

1
1
1
1
1
1
1
1

Sample Input 4

20 50 12
1 10 25
11 20 5
21 30 40
31 40 15
41 50 1
5 25 33
26 45 12
1 3 50
48 50 7
7 18 22
19 32 44
33 44 9
9 9 30
30 35 2
2 8 16
16 16 41
41 49 6
6 14 28
28 38 11
11 27 35
1 50
1 10
11 20
21 30
31 40
41 50
5 45
13 37
25 25
2 49
17 33
39 50

Sample Output 4

1
1
1
1
1
1
1
1
1
1
1
1

Sample Input 5

1 1 1
1 1 1
1 1

Sample Output 5

1