問題一覧 > 通常問題

No.1758 Lazy Segment Tree...?

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan tokusakuraitokusakurai
1 ProblemId : 7108 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-20 20:44:32

問題文

PCT 君は以下のような問題を作りました。

Lazy Segment Tree

$0$ で初期化された長さ $N$ の数列 $A_0,A_1,\dots,A_{N-1}$ があります。

数列 $A$ に対して $Q$ 個のクエリを処理してください。クエリは以下の $2$ 形式のどちらかです。

  • $1\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ $L_i \leqq j < R_i$ を満たす $j$ に対して $A_j$ を $1-A_j$ に変更する。
  • $2\ L_i\ R_i\ (0 \leqq L_i < R_i \leqq N) \cdots$ $A_{L_i}$ から $A_{R_i-1}$ の転倒数を出力する。

この問題は Nyaan さんにはあまりにも簡単だったため、PCT 君は問題を以下のように変更しました。

Lazy Segment Tree...?

$N,Q$ が与えられた時 Lazy Segment Tree の入力としてあり得るものは $(N(N+1))^Q$ 通り存在しますが、その全てに対しての「出力する値の総和」の総和を $998244353$ で割ったあまりを求めてください。

Lazy Segment Tree...? を解いてください。

制約

  • 入力は全て整数である。
  • $2 \le N,Q \le 2 \times 10^5$

入力

$N\ Q$

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
2 2
出力
1

この場合、以下の入力ケースが唯一出力する値の総和が正になるケースです。

1 0 1
2 0 2

始め数列は $(0,0)$ となっています。

$1$ 個目のクエリで $(1,0)$ に変更されます。

$2$ 個目のクエリで $(1,0)$ の転倒数 $1$ を出力します。

よって出力する値の総和は $1$ となります。

サンプル2
入力
4 5
出力
1747840

サンプル3
入力
1234 5678
出力
492570703

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。