問題一覧 > 通常問題

No.1758 Lazy Segment Tree...?

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 15
作問者 : PCTprobability / テスター : NyaanNyaan tokusakurai
お気に入りにしたユーザー ProblemId : 7108 / 自分の提出
問題文最終更新日: 2021-12-29 18:50:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 324 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。