Ex - Max Limited Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の整数列 A = (A_1, \dots, A_N) であって、以下の条件を全て満たすものの総数を 998244353 で割った余りを求めてください。

  • 1 \leq i \leq N を満たす全ての i について、0 \leq A_i \leq M
  • 1 \leq j \leq Q を満たす全ての j について、A_{L_j}, \dots, A_{R_j} の最大値は X_j である。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \lt 998244353
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N \, (1 \leq i \leq Q)
  • 1 \leq X_i \leq M \, (1 \leq i \leq Q)
  • 入力は全て整数

入力

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

N M Q
L_1 R_1 X_1
\vdots
L_Q R_Q X_Q

出力

答えを出力せよ。

入力例 1

3 3 2
1 2 2
2 3 3

出力例 1

5

A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3) が条件を満たします。

入力例 2

1 1 1
1 1 1

出力例 2

1

入力例 3

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

出力例 3

135282163

Score : 600 points

Problem Statement

Find the number, modulo 998244353, of integer sequences A = (A_1, \dots, A_N) of length N that satisfy all of the following conditions:

  • 0 \leq A_i \leq M for all i such that 1 \leq i \leq N.
  • The maximum value of A_{L_j}, \dots, A_{R_j} is X_j for all j such that 1 \leq j \leq Q.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \lt 998244353
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N \, (1 \leq i \leq Q)
  • 1 \leq X_i \leq M \, (1 \leq i \leq Q)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1 X_1
\vdots
L_Q R_Q X_Q

Output

Print the answer.

Sample Input 1

3 3 2
1 2 2
2 3 3

Sample Output 1

5

A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3) satisfy the conditions.

Sample Input 2

1 1 1
1 1 1

Sample Output 2

1

Sample Input 3

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

Sample Output 3

135282163