遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…

この問題は、人生で最初に挑む遅延セグ木の問題としてオススメ！Starry Sky Tree と呼ばれるものでもある。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s…

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね！！！ 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。 今、文字列中の 個の連続する区間 ( 番目の区間を とします) が与えら…

セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい！ 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…

これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …

区間加算に対応したデータ構造の出番！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする！！！ 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…