コンテスト後のツイート
F 区間加算、区間minの遅延セグ木とBITを使う。区間内でk未満のところがあれば、そこを答えに加え、セグ木で+1<<63し、BITで+1（加算する箇所は高々N個）する。それ以外はkなので掛け算で値は求まる。一回TLEしたのは、何度も+1<<63して64bit型整数を超えたため。そこを修正したら2s切りました。
— titia (@titia_til) October 4, 2025
G - Range Knapsack Query
解説放送を見てAC。
自力で思いつくのは難しいが、知ってしまえば単純な内容。
分割統治で答えを求める……と言われてもなぜそれで計算量が落ちるのかピンと来なかったが、noshiさんによるDisjoint Sparse Tableの図を見ると分かりやすかった。
これをデータ構造として持つのがDisjoint Sparse Tableですね。今回はクエリ先読みできるので分割統治で、この図のようなことをやる（上のノードから下のノードへ分割し、潜っていく）とOK。
なお、実装にも苦戦しました。分割統治したデータを持とうとするとMLEしたのが一つ。また、クエリでl=rの場合での場合分けが必要で、そこにもなかなか気付きませんでした。
0 件のコメント:
コメントを投稿