分数: 1000 点
问题陈述
Yosupo 喜欢查询问题。他提出了如下问题:
一个查询问题
我们有一个长度为的整数序列 N: a_1,\ldots,a_N。最初, a_i = 0 (1 \leq i \leq N)。 我们还有一个变量 ans,最初是 0。 在这里,你将获得 Q 以下形式的查询:
类型 1:
t_i (=1) l_i r_i v_i
对于每个 j = l_i,\ldots,r_i, a_j := \min(a_j,v_i).
类型 2:
t_i (=2) l_i r_i v_i
对于每个 j = l_i,\ldots,r_i, a_j := \max(a_j,v_i).
类型 3:
t_i (=3) l_i r_i
计算 a_{l_i} + \ldots + a_{r_i} 并将结果添加到 ans.
打印最终值 ans.
这里,对于每个查询, 1 \leq l_i \leq r_i \leq N 成立。另外,对于类型 1 和类型 2, 0 \leq v_i \leq M-1 成立。
Maroon看到这个问题,觉得太简单了,于是想出了下面的问题:
查询问题
给定的是正整数 N,M,Q。有 ( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q “查询问题”的有效输入。求所有这些输入的输出总和,模数 998{,}244{,}353.
找到它。
约束
- 1 \leq N,M,Q \leq 200000
- 输入的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
N M Q
输出
打印答案。
样本输入 1
1 2 2
示例输出 1
1
有 25 有效输入,并且只有其中一个 - 如下所示 - 会产生正值 ans.
t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1
ans 将是 1 在这种情况下,所以答案是 AtCoder 线沿线的 1.
示例输入 2
3 1 4
示例输出 2
0
示例输入 3
111 112 113
示例输出 3
451848306