データ構造に関するカテゴリーです。

AtCoder, セグメント木, 動的計画法

問題方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...

Codeforces, フェニック木

問題方針

バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。

コード参考

AtCoder, 動的計画法, 累積和, 遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...

yukicoder, セグメント木, 数学

問題方針

関節 \( i \) の位置を \( P_i = (x_i, y_i) \) とします。初期値は、\( P_i = (i, 0) \) となり、\( P_0 = (0, 0) \) となります。ここで、ベクトル  \( \bo ...

AtCoder, データ構造, 実装

問題方針

ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。

ここで、幼稚園 \( i \) のレートの集合を ...

AtCoder, セグメント木

問題方針

区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...

AtCoder, セグメント木, 二分探索, 整列

問題方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...

AOJ, セグメント木, データ構造

問題方針

点数が更新されたとき、その時点で最も高い得点を持つチームの番号が分かればよいので、セグメント木を使います。クエリは全区間を対象とするので、根の値が最も高い得点を持つチームの番号となります。

コード

&nbs

AOJ, セグメント木, データ構造

問題方針

平方分割でこの問題を解いたことがありますが、セグメント木を使って解きました。

コード

 

yukicoder, データ構造

問題方針

カンニングされた人がカンニングを行っていないかどうかを調べます。これはセットを使って実現することができます。

コード