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)\) 時間で処理できます。

提出コード