C - Removal of Multiples Editorial
by 
maspy
ヒント集 → https://atcoder.jp/contests/arc197/editorial/12811
\(n = \max\{Q, \max_i B_i\}\) として，これを計算量を表す際に使います．
[1] 答の上界
問題文に「\(S\) はこの時点で \(B_i\) 個以上の要素を含むことが証明できる」と書かれています．まずはこのことを証明しましょう．
素数を昇順に \(p_1=2, p_2=3, p_3=5, \ldots\) とします． 素数 \(p_k\) が削除されるのは，\(A_i=p_k\) となるクエリが来た場合に限られます．
したがって，\(Q\) 回以下の削除操作では，必ず \(p_1, \ldots, p_{Q+B_i}\) のうち \(B_i\) 個以上の要素が削除されずに残っています．
したがって答は \(p_{2n}\) 以下になります．本問の制約では答が常に \(p_{200000} = 2750159\) 以下であることが分かります．なお，\(p_{2n}=\Theta(n\log n)\) が知られています．
[2] クエリ処理
[1] で求めた答の上界を \(N=p_{2n}\) としましょう．
\(S\) は無限集合ですが，そのうち \(N\) 以下であるもの全体を管理しましょう．
\(N\) 以下の整数からなる集合を扱う何らかのデータ構造（後述）を用意します．クエリにおける削除操作では，愚直なクエリ処理に簡単な枝狩りを追加したアルゴリズムを考えます．
- \(a=A_i\) というクエリが来たとする．過去にも同じ \(a\) に対するクエリが来ているならば，何もしない．そうでなければ，\(N\) 以下のすべての \(a\) の倍数すべてについて，過去に削除操作が行われているかを調べて，行われていないならばデータ構造から削除する．
すると，本問を解くのに必要な計算量は以下の和になります．
- クエリのたびにデータ構造から削除すべき値を列挙する：\(O(Q + N\log N)\) 時間．
- データ構造から値を削除する回数：\(O(N)\) 回．
- データ構造から \(b\) 番目の値を検索する回数：\(O(Q)\) 回．
\(2\) 番目，\(3\) 番目は明らかです．\(1\) 番目の計算量は，\(\sum_{a\geq1} \lfloor N/a\rfloor=O(N\log N)\) という有名な評価から分かります．
本問の制約でこれらを余裕を持って行える解法をいくつか紹介します．
[2-1] セグメント木（Segment Tree）
セグメント木を利用すると，データ構造からの値の削除，\(b\) 番目の値の検索がどちらも \(O(\log N)\) 時間で行えるため，本問を \(O(N\log N)\) 時間（したがって \(O(n\log^2n)\) 時間）で解くことができます．
なお，\(b\) 番目の値の検索に \(O(\log^2 N)\) 時間かかる実装をした場合でも，計算量オーダーはやはり \(O(n\log^2n)\) 時間のままです．
[2-2] Fenwick 木（Fenwick Tree）
Fenwick 木を利用すると，データ構造からの値の削除，\(b\) 番目の値の検索がどちらも \(O(\log N)\) 時間で行えるため，本問を \(O(N\log N)\) 時間（したがって \(O(n\log^2n)\) 時間）で解くことができます．計算量オーダーはセグメント木と同様ですが，こちらの方が定数倍が良くなります．
[2-3] 平方分割（Sqrt Decomposition）
適当なバケットサイズ \(S\) をとり，区間 \([1,N]\) を \(\lceil N/S\rceil\) 個の長さ \(S\) のバケットに分割します．各要素の状態に加えて，各バケット内での要素数を管理します．
すると，データ構造からの値の削除が \(O(1)\) 時間，\(b\) 番目の値の検索が \(O(N/S+S)\) 時間で行えます．\(S\) を適切にとれば，検索が \(O(\sqrt{N})\) 時間になります．したがって本問を計算量 \(O(N+Q\sqrt{N})\) 時間（\(O(n\sqrt{n\log n})\) 時間）で解くことができます．
posted:
last update: