USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿
重量値セグメント木と動的ノード作成
目次- ブルートフォース法 (1)
ブルートフォース法 (2)
重量値セグメント木
演習問題
はじめに主席木を学習中に、重量値セグメント木の学習ノートを更新しておくのを思い出しました
まず、以下の問題を考えてみましょう：
配列に対して以下の操作を行います：
操作 (1)：配列中の第k小さい要素を問い合せます（答えは存在すると仮定）。
操作 (2)：ある要素を変更しま ...
5月28日 02:10 投稿
基環樹構造上の動的計画法：アルゴリズム設計と実装手法
基環樹の定義と構造的特徴
基環樹（Base Ring Tree）とは、ノード数と辺数が等しく、かつ連結なグラフ構造を指します。その最大の特徴は、グラフ内に閉路（サイクル）がちょうど一つだけ存在することです。グラフが非連結であり、各連結成分がノード数と辺数を一致させる場合は「基環樹森」と分類されます。通常の木構造を対象とした動的計画法（木DP）と比較すると、閉路 ...
5月13日 16:44 投稿