問題一覧 > 通常問題

No.2611 Count 01

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
0 ProblemId : 8897 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-19 19:03:37

問題文

以下では、 01 のみからなる文字列を $01$ 列と呼びます。

$01$ 列 $x$ に対し、 $f \left( x \right)$ を $x$ が含む 0 の数と 1 の数の積とします。
また $g \left( x \right)$ を以下のように定めます。

  • $|x| = n$ として $\frac{n \left( n+1 \right)}{2}$ 通りある $x$ の連続部分文字列 $x'$ 全てについて、 $f \left( x' \right)$ を足し合わせた値。

長さ $N$ の $01$ 列 $S$ が与えられます。 $Q$ 個のクエリが与えられるので、順に処理してください。
クエリは次の $2$ 種類のいずれかです。

  • 1 i : $S$ の $i$ 文字目を入れ替える。すなわち $i$ 文字目が 0 なら 1 に、 1 なら 0 にする。(変更クエリ)
  • 2 l r : $S$ の $l$ 文字目から $r$ 文字目までの部分文字列を $S'$ とする。 $g \left( S' \right)$ を $998244353$ で割った余りを出力する。(出力クエリ)

入力

$N\ \ Q$
$S$
$\mathrm{query}1$
$\mathrm{query}2$
$\vdots$
$\mathrm{query}Q$
各クエリでの入力は以下に示す $2$ つの形式のいずれかです。
1 i
2 l r

  • $1 \leq N,Q \leq 1.5 \times 10^5$
  • $S$ は長さ $N$ の $01$ 列
  • $1 \leq i \leq N$
  • $1 \leq l \leq r \leq N$
  • $N,Q,i,l,r$ は全て整数
  • 出力クエリは $1$ 個以上与えられる

出力

出力クエリが $M$ 個あるとして $M$ 行出力してください。 $m$ 行目には出力クエリの中で $m$ 番目のクエリに対応する答えを出力してください。

サンプル

サンプル1
入力
6 6
010110
2 1 3
1 3
2 4 5
1 5
2 4 5
2 1 1
出力
4
0
1
0

  • $1$ 番目のクエリにおいて $S'$ は 010 なので $g \left( S' \right) = 4$ です。
  • $2$ 番目のクエリの後、 $S$ は 011110 です。
  • $3$ 番目のクエリにおいて $S'$ は 11 なので $g \left( S' \right) = 0$ です。
  • $4$ 番目のクエリの後、 $S$ は 011100 です。
  • $5$ 番目のクエリにおいて $S'$ は 10 なので $g \left( S' \right) = 1$ です。
  • $6$ 番目のクエリにおいて $S'$ は 0 なので $g \left( S' \right) = 0$ です。

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

サンプル3
入力
38 17
00011111001010001001101100101011101110
2 12 19
1 8
2 25 36
1 19
2 1 11
2 1 3
2 6 33
2 14 21
1 8
2 7 12
2 5 36
2 29 35
2 17 18
1 16
1 9
2 11 25
1 27
出力
100
529
387
0
14391
112
43
24138
64
1
1236

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