セグメント木に関するカテゴリー
[AtCoder] ACL Beginner Contest D – Flat Subsequence
問題方針
最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。
まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...
[yukicoder] No. 1226 I hate Robot Arms
問題方針
関節 \( i \) の位置を \( P_i = (x_i, y_i) \) とします。初期値は、\( P_i = (i, 0) \) となり、\( P_0 = (0, 0) \) となります。ここで、ベクトル \ ...
[AtCoder] ABC 157 E – Simple String Queries
問題方針
区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...
[AtCoder] ABC 153 F – Silver Fox vs Monster
問題方針
モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。
最適な攻撃方法最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...
[AOJ] No. 0282 プログラミングコンテスト
問題方針
点数が更新されたとき、その時点で最も高い得点を持つチームの番号が分かればよいので、セグメント木を使います。クエリは全区間を対象とするので、根の値が最も高い得点を持つチームの番号となります。
コード#include < ...
[AOJ] DSL_2_A Range Minimum Query (RMQ)
問題方針
平方分割でこの問題を解いたことがありますが、セグメント木を使って解きました。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll; ...
[AOJ] DPL 1 D 最長増加部分列
問題方針
LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。
動的計画法と二分探索参考を参照してください。 ...