UVA10902 Pick-up Sticks 問題の幾何学的解法
N本の棒（線分）が与えられます。これらの棒は順に入力され、各棒の両端の座標で定義されます。後の棒が前の棒と交差する場合、後の棒は前の棒を「遮る」と見なされます。この問題では、最終的にどの棒にも遮られずに残る棒の数を求めます。
制約として、Nは最大10^5ですが、最終的な解答（遮られない棒の数）は1000を超えないことが保証されています。
幾何アルゴリズム ...
10月12日 22:44 投稿
USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿