No.1758 Lazy Segment Tree...?
タグ : / 解いたユーザー数 15
作問者 :
PCTprobability
/ テスター :
Problem Statement
PCT created the following problem.
Lazy Segment Tree
There is a sequence $A_0,A_1,\dots,A_{N-1}$ of length $N$, initialized with $0$.
Process $Q$ queries on the sequence $A$. Each query is of one of the following $2$ types.
- $1\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ For each $j$ satisfying $L_i \leqq j < R_i$, change $A_j$ to $1-A_j$.
- $2\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ Output the inversion number of $A_{L_i}$ through $A_{R_i-1}$.
Since this problem was far too easy for Nyaan, PCT changed it as follows.
Lazy Segment Tree...?
Given $N,Q$, there are $(N(N+1))^Q$ possible inputs to Lazy Segment Tree. Over all of them, find the sum of "the sum of the output values", modulo $998244353$.
Solve Lazy Segment Tree...?.
Constraints
- All input values are integers.
- $2 \le N,Q \le 2 \times 10^5$
Input
$N\ Q$
Output
Output the answer in $1$ line.
Sample
Sample 1
Input
2 2
Output
1
In this case, the following input is the only one for which the sum of the output values is positive.
1 0 1 2 0 2
Initially, the sequence is $(0,0)$.
Query $1$ changes it to $(1,0)$.
Query $2$ outputs $1$, the inversion number of $(1,0)$.
Therefore, the sum of the output values is $1$.
Sample 2
Input
4 5
Output
1747840
Sample 3
Input
1234 5678
Output
492570703
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。