公式

C - Removal of Multiples 解説 by evima

Hints: https://atcoder.jp/contests/arc197/editorial/12878

Let \(n = \max\{Q, \max_i B_i\}\); we will use it in our complexity estimates.

[1] Upper bound on the answer

The problem statement asserts that after each deletion, \(S\) still contains at least \(B_i\) elements. Let us prove this first.

List the primes in ascending order as \(p_1=2,p_2=3,p_3=5,\ldots\). A prime \(p_k\) can only be deleted when a query \(A_i=p_k\) appears.

Hence, after at most \(Q\) deletion operations, among the primes \(p_1,\ldots,p_{Q+B_i}\) at least \(B_i\) remain.

It follows that the answer is at most \(p_{2n}\). Under our constraints, it is at most \(p_{200000}=2750159\). (It is known that \(p_{2n}=\Theta(n\log n)\).)

[2] Processing the queries

Let \(N=p_{2n}\) be the upper bound found in [1].

Among the elements of the infinite set \(S\), we manage only those that are at most \(N\).

We use some data structure (explained below) that handles a set of integers at most \(N\). In the deleting operation of a query, we do a simple pruning in addition to a naive processing:

  • Upon receiving a query \(a=A_i\), if we have processed \(a\) before, do nothing. Otherwise, for each multiple of \(a\), examine if it is already deleted, and if it is not yet deleted then delete it from the data structure.

Then, the total time it takes to solve the problem is the sum of the following:

  • List the values to be deleted for each query: \(O(Q + N\log N)\) time.
  • The number of deletions of a value: \(O(N)\) times.
  • The number of times the \(b\)-th smallest value is retrieved: \(O(Q)\) times.

The second and third estimates are obvious. The first complexity follows from the well-known bound \(\sum_{a\geq1} \lfloor N/a\rfloor=O(N\log N)\).

Below are several methods that achieve this:

[2-1] Segment Tree

Both the deletion and the \(b\)-th-element retrieval take \(O(\log N)\) time, allowing us to solve the problem in \(O(N\log N)\) time (that is, \(O(n\log^2n)\) time).

The total complexity will still be \(O(n\log^2n)\) even if the \(b\)-th-element retrieval takes \(O(\log^2 N)\) time.

[2-2] Fenwick Tree

Both the deletion and the \(b\)-th-element retrieval take \(O(\log N)\) time, allowing us to solve the problem in \(O(N\log N)\) time (that is, \(O(n\log^2n)\) time), but with a better constant factor compared to Segment Tree.

[2-3] Square-Root Decomposition

Choose some bucket size \(S\), and partition the segment \([1,N]\) into \(\lceil N/S\rceil\) buckets of size \(S\). Maintain the number of elements in each bucket, in addition to the state of each element.

Then, the deletion takes \(O(1)\) time, and the \(b\)-th-element retrieval takes \(O(N/S + S)\) time. A proper choice of \(S\) makes the retrieval run in \(O(\sqrt{N})\) time, allowing us to solve the problem in \(O(N+Q\sqrt{N})\) time (\(O(n\sqrt{n\log n})\) time).

投稿日時:
最終更新: