D - Cutting Woods 解説 by rsk0315
word size \(w\) に対して \(O(L/w+Q)\) 時間のアルゴリズムを書きます。
前提知識
この解説 の後半で言及されているデータ構造を使います。これにより、
- \(A\subseteq \{0, 1, \dots, L\}\) に対して \(S \gets A\) で初期化
- \(O(L/w+|A|)\) 時間
- \(S \gets S \setminus \{i\}\) で更新 (remove)
- ならし \(O(1)\) 時間
- 与えられた \(i\) に対して \(\max\,\{j\in S\mid j\lt i\}\) を求める (predecessor)
- 与えられた \(i\) に対して \(\min\,\{j\in S\mid j\gt i\}\) を求める (successor)
- これらもならし \(O(1)\) 時間
ができます。
解法
まず、クエリを先読みして、1
のクエリで聞かれる \(p\) たちからなる集合を \(P\) とし、\(S \gets P \cup \{0, L\}\) で初期化します。
クエリを後ろから順に見て、1
のクエリに対しては remove を、2
のクエリに対しては predecessor と successor を用いることで、一つあたり (amortized) \(O(1)\) 時間で処理できます。
投稿日時:
最終更新: