他の方々のブログ等を参考にしながら書き直してみました*2。詳細は後述しますが、tsutajさん・ei1333さん・beetさんのお三方の解説を大いに参考にさせていただきました。変数名やメソッド名はそれぞれの記事から拝借しているため、若干キメラになっていて読みにくいかもしれません。数学的な側面の理解が浅いので、モノイド・作用素モノイド周りの命名が特に気持ち悪いかもしれません*3。)を適切に書き換えることだけに注力すれば、うまく動くのではないかと思います。RSQ)は検証済みです*4。最小値に加えて、最小値が入っているインデックスをもたせた構造体を要素の型とすればOKです。以下はコードの抜粋です(提出はこちら)。みたいなことを書いてしまいました。次の例に示すように、別にそうとも限らないですね。それらに関する関数オブジェクトを適切に決定することに注力しさえすればいいように書いたつもりです。いうようなもの*5のようです。区間加算を真に受けて遅延伝搬セグメントツリーでも解けます。与えられた定義で計算される圧縮値の他、区間の両端の値をもたせた構造体を要素の型とすればOKです。単位元は少し注意が必要です。以下はコードの抜粋です(提出はこちら)。学習の高速道路が整備されていてありがたいなぁと感じました。tsutajさんの解説tsutajさんの解説記事(遅延伝搬なし)tsutajさんの解説記事(遅延伝搬あり)いずれもとてもわかりやすく、初学時にセグメントツリーの仕組みを理解するのにはかどりました*6。セグメント木の抽象化だけに絞るのであれば、tsutajさんのブログを理解すれば十分な気がします。遅延伝搬セグメントツリーの抽象化は独力ではできる気がしなかったため、非常に参考になりました。お二方とも旧ブログの方を参照してしまって恐縮です。beetさんの記事の方は本当に丁寧に説明されていてわかりやすかったです。少数の定義を渡すだけで正しく動いてくれて感動したので、個人的には満足しています。運用して様子見してみようと思います。*1:解説で「セグメントツリーでも解けます」とあるときにテンション下がるのは嫌ですよね。*2:言語を変えただけで、基本的に写経です。*3:アドリブでいじるときに、自分にとって意味を思い出しやすいように意識して書いたらこうなりました*4:Tの型が複雑になるときのインスタンス化の速度への影響が、まだ十分に検証しきれていません。*5:そちらの解法で解き直していないので間違っているかもしれません。D2復習コンテスト中に解けなかったものの復習です。BITを使った方法が一番自分にとって与し易かったため、BITで解きました。この数列に対して部分列(間の要素を好きなだけ削除し、残ったものの順番を変えずに得られる数列)を考える。与えられたとき、以下の条件を満たす部分列はoptimalであるという。あらゆる部分列の中で、部分列の要素の総和が最大となる。1の条件を満たす部分列の中で、元の数列の位置に関して辞書順最小である。個のクエリが与えられる。番目の値」を答える必要がある。すべてのクエリに対して、それらの順番どおりに答えよ。k解答Easyバージョンは制約が小さいため、愚直な解法で通りますが、こちらは賢くクエリを処理する必要があります。個の数を選択したものとなります。2の条件より、同じ要素が元の数列に複数存在する場合、できるだけ元の数列において前の方の位置に登場したものを優先的に選ぶ必要があります。要素の大きさを基準に降順となるようにし、値が同じ場合は元の数列における位置に関して昇順となるようにソートします。番目に小さい要素の値を出力すればOKです。要素取得するたびにそれらを位置に関して昇順ソートする必要があります。これは許容できないため、工夫が必要です。小さい順に答えていくという工夫ができます。することで、(許されるなら)ソートしたい集合が、単純に新しい要素がappendされていくだけとなり、シンプルになります。「要素の追加」と「特定の順番の値の取得」を高速に行う必要があります。