AtCoder Beginner Contest 430

　Fまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 430 Fまで。
A 論理の問題だけど、読解が難しい
B 全列挙
C 尺取り。
D tatyamさんのSortedSetで。
E Rolling Hash。mod一個で投げてWAを出した。
F グラフにして子孫の数を数えると、左右から何番目以降になるかが分かる。
G x<=60を使いそうだが、何も分からない。

— titia (@titia_til) November 1, 2025

G - Range Set Modifying Query

　解説放送を見てAC。

　Segment Tree Beatsを初めて実装した。非常に苦労した。

　そもそも、何を持つ必要があるか理解するのが難しい。

SEG=[0]*(2*seg_el) # max(bit_count)が最大なものの素の値

SEG2=[ALL]*(2*seg_el)# SEG[i*2]とSEG[i*2+1]での共通bit

SEG3=[0]*(2*seg_el) # bit_count()の最大値

SEG4=[0]*(2*seg_el) # 最大値を取る要素数

LAZY0=[0]*(2*seg_el) # 遅延伝搬すべき要素。追加の場合。SEG2が1のbitのみ、下へ伝播する。

LAZY1=[0]*(2*seg_el) # 遅延伝搬すべき要素。削除の場合。SEG2が1のbitのみ、下へ伝播する。

　と定義してやったが、LAZYが二つ必要なことに気付かず、ずっと悩んでしまった。

　ちゃんと抽象化していたとしても、ここで悩んでしまったと思う。

　そして、最後まで引っ掛かったのは、[L,R)の範囲外でも、updates内で下のノードへ行かなくてはいけないときも、遅延伝搬を行わなくてはいけないところでした。

　ここはデータ構造を理解していれば（あるいは、ライブラリを整備していれば）引っ掛からなかったはずのところ。こっちのミスは減らせますね。