AtCoder Beginner Contest 250 E問題 Prefix Equality
問題
提出解答
問題の概要
とする. 次の
個の質問
に答えよ.
- 質問
:
か?
制約
解法
する.
次のようにして定義された列 を用いて,
かどうかを判定できる.
の定義
に対して,
のとき,
かつ,
に対して, 「
ならば,
」が成り立つとき,
, それ以外は
.
の定義
に対して,
のとき,
ならば,
,
ならば,
.
このとき,
である.
ここで, と
の関係性について,
. つまり,
ならば,
である.
であり,
となる
が存在するとき, このような
のうち最小の整数を
として,
である.
同様に, と
の関係性について,
. つまり,
ならば,
である.
であるとき,
となる全ての
の集合を
としたとき,
である.
よって, 各クエリに対して, 加法に関する1点更新と区間和の処理が必要なので, BIT によって高速処理できる.
クエリ先読みにより, の昇順毎に
を更新することにしていくと, 1点更新は各要素高々1回なので,
個の質問を全て合わせて
で処理できる,
なお, を
とすると,
となり, 空間の節約になる.