AT_abc262_h [ABC262Ex] Max Limited Sequence
题目描述
### 题目大意
求满足以下条件的长度为 $N$ 的序列 $A=(A_1,A_2,\cdots A_N)$ 有多少种：
+ $\forall i \in[1,N],0\leq A_i\leq M$
+ $\forall i \in[1,Q],\max \limits_{L_i\leq j\leq R_i}A_j=X_i$
输入格式
第一行输入 $3$ 个正整数 $N,M,Q$
后面 $Q$ 行每行 $3$ 个正整数表示 $L_i,R_i,X_i$
$1\leq N\leq 2\times 10^5$
$1\leq M
输出格式
输出满足条件的序列数，对 $998244353$ 取模。
说明/提示
### 制約
- $ 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) $
- 入力は全て整数
### Sample Explanation 1
$ A\ =\ (0,\ 2,\ 3),\ (1,\ 2,\ 3),\ (2,\ 0,\ 3),\ (2,\ 1,\ 3),\ (2,\ 2,\ 3) $ が条件を満たします。