/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
yosupoくんはクエリの問題が大好きなので、次のような問題を作りました。
A Query Problem
長さ N の整数列 a_1,\ldots,a_N があります。はじめは a_i = 0 (1 \leq i \leq N) です。 また、ans という変数があり、はじめは 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くんは簡単すぎると感じたため、次の問題を考えました。
Query Problems
正整数 N,M,Q が与えられます。問題 "A Query Problem" に対する入力は ( \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 になるので、答えは 1 です。
入力例 2
3 1 4
出力例 2
0
入力例 3
111 112 113
出力例 3
451848306
Score : 1000 points
Problem Statement
Yosupo loves query problems. He made the following problem:
A Query Problem
We have an integer sequence of length N: a_1,\ldots,a_N. Initially, a_i = 0 (1 \leq i \leq N). We also have a variable ans, which is initially 0. Here, you will be given Q queries of the following forms:
Type 1:
t_i (=1) l_i r_i v_i
For each j = l_i,\ldots,r_i, a_j := \min(a_j,v_i).
Type 2:
t_i (=2) l_i r_i v_i
For each j = l_i,\ldots,r_i, a_j := \max(a_j,v_i).
Type 3:
t_i (=3) l_i r_i
Compute a_{l_i} + \ldots + a_{r_i} and add the result to ans.
Print the final value of ans.
Here, for each query, 1 \leq l_i \leq r_i \leq N holds. Additionally, for Type 1 and 2, 0 \leq v_i \leq M-1 holds.
Maroon saw this problem, thought it was too easy, and came up with the following problem:
Query Problems
Given are positive integers N,M,Q. There are ( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q valid inputs for "A Query Problem". Find the sum of outputs over all those inputs, modulo 998{,}244{,}353.
Find it.
Constraints
- 1 \leq N,M,Q \leq 200000
- All numbers in input are integers.
Input
Input is given from Standard Input in the following format:
N M Q
Output
Print the answer.
Sample Input 1
1 2 2
Sample Output 1
1
There are 25 valid inputs, and just one of them - shown below - results in a positive value of ans.
t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1
ans will be 1 in this case, so the answer is 1.
Sample Input 2
3 1 4
Sample Output 2
0
Sample Input 3
111 112 113
Sample Output 3
451848306