セグメント木
こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …
いもす法 問題へのリンク editorial 問題概要 要素からなる数列がある。初期状態では全要素の値が 0 である。以下の 回の操作を行なって得られる数列を出力せよ。 各クエリでは整数 が与えられる。区間 に対して、初項 1、交差 1 の等差数列を加算する 制約 …
まさに遅延評価セグメント木の練習問題！！！ 問題へのリンク 問題概要 長さ の文字列 S がある。 最初は のすべての文字が 1 である。以下の 回のクエリに答えよ。 各クエリは整数 が与えられる () の 番目から 番目までをすべて に書き換える を数値とみな…
LIS を求める in-place DP を応用すればできる！ でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった！ in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…
早速遅延セグ木があればできる問題来た！！ AC Library の出番かと思った！！！ 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…
実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう！ 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…
一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1： の 文字目を に変更する タイプ 2： の区間 に含まれる文字の種類数を答える …
セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい！ 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…
面白かった。セグ木にこういうの乗っけるの楽しい！ 問題へのリンク 問題概要 の盤面の各マスに整数値が書かれている。このマスに対して、適切に を決めて、 盤面の 0 行目の区間 の総和 盤面の 1 行目の区間 の総和 盤面の 2 行目の区間 の総和 盤面の 3 行…
BinaryTrie を確認した！！！ 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…
これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …
区間加算に対応したデータ構造の出番！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…
実家なんだと思うけど...意外とはまりやすい問題な気 がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…
「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする！！！ 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…
これと似てる！！！ これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […
こういうのを得意になるぞー！！！ でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…
最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…
遅延評価セグメントツリーで殴った...速度重視ならそれでいい気もする 問題へのリンク 問題概要 本の竹があって、時刻 0 においてすべての竹の高さは 0 である。それぞれの竹は時刻が 1 経過するごとに高さが 1 増える。 竹を伐採するイベントが 回予定され…
いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…
オイラーツアー第4弾！！！ でもせっかくなので色んな方法で解いてみた！！！ Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初期状…
オイラーツアー第三弾！ RUPC 2018 で見たばかりの問題でもある。 問題へのリンク 問題概要 頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ: v: 頂点 v を根とす…
オイラーツアーの練習に解いたけど、発想も面白いん！！！ 問題へのリンク 問題概要 頂点 1 を根とする、頂点数 N の根付き木がある。以下の Q 個のクエリに答えよ: M 個の頂点 v1, v2, ..., vM に実をつける。「その頂点を根とする部分木に含まれる実の個数…
セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…
