セグメント木に関するカテゴリー

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

問題方針

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

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

yukicoder,セグメント木,数学

問題方針

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

AtCoder,セグメント木

問題方針

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

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

問題方針

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

最適な攻撃方法

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

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

問題方針

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

コード#include < ...

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

問題方針

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

コード#include <bits/stdc++.h>using namespace std;typedef long long ll; ...

AOJ,セグメント木,二分探索,動的計画法,探索

問題方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法と二分探索

参考を参照してください。 ...