201115: [AtCoder]ARC111 F - Do you like query problems?

Memory Limit:1024 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

给出三个数 $n,m,q$。 你有一个长度为 $n$ 的序列 $a$,初始全为为 $0$,你有三种操作: 操作 $1$:给出 $l,r,v$,让区间 $[l,r]$ 对 $v$ 取 $\min$。 操作 $2$:给出 $l,r,v$,让区间 $[l,r]$ 对 $v$ 取 $\max$。 操作 $3$,给出 $l,r$,求区间和,将其累加进一个叫 $sum$ 的变量里。 **你并不需要维护这个数据结构**,而是统计一共有 $q$ 个操作的情况下,所有不同的操作序列中 $3$ 操作得到的 $sum$ 的总和,对 $998244353$ 取模。你需要保证 $v\in[0,m-1]$。

加入题单

上一题 下一题 算法标签: