Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - Linear Probing Editorial by en_translator

### Naive solution

Suppose that we naively increment $$h$$ step-by-step for every query of $$t_i = 1$$. This method may cost $$\Theta (Q^2)$$, for example for the following query:

• For every query, $$t_i = 1$$ and $$x_i \bmod N = 0$$.

### Solution 1

The set of $$i$$ such that $$A_i = -1$$ can be expressed as the union of $$O(Q)$$ number of segments. Assume that the segments can be expressed as $$[l_1, r_1), [l_2, r_2), \dots, [l_n, r_n)$$, where $$l_1 \lt r_1 \lt l_2 \lt r_2 \lt \dots \lt l_n \lt r_n$$.

For $$0 \leq h \lt N$$, consider incrementing $$h$$ one by one until it becomes $$A_{h \bmod N} = -1$$; let $$p(h)$$ be first such $$h \bmod N$$.

• If $$r_n \leq h$$, then $$p(h) = l_1$$.
• If $$h \lt r_n$$, let $$m$$ be the minimum $$k$$ such that $$h \lt r_k$$, then:
• if $$l_m \leq h$$, then $$p(h) = h$$;
• if $$h \lt l_m$$, then $$p(h) = l_m$$.

For the query of $$t_i = 1$$, denoting $$k = p(x_i \bmod N)$$, we can let $$A_k \leftarrow x_i$$. Then, we need to update $$[l_1, r_1), [l_2, r_2), \dots, [l_n, r_n)$$ as follows:

• Take the unique segment $$l_m \leq k \lt r_m$$ and remove $$[l_m, r_m)$$.
• If $$l_m \lt k$$, then add $$[l_m, k)$$ anew.
• If $$k + 1 \lt r_m$$, then add $$[k + 1, r_m)$$ anew.

Adding/removing segments and finding minimum $$k$$ such that $$h \lt r_k$$ can be done in an $$O(\log Q)$$ time with data structures like balanced binary search tree or Fenwick tree. In C++, we may use std::set or std::map.

If we manage all elements with an array, we can read and write the values of $$A_i$$ in a total space complexity of $$\Theta (N)$$ and in an $$O(1)$$ time per query; if we use dictionary types to store only elements with $$A_i \neq -1$$, it will cost a total space complexity of $$O(Q)$$ and a time complexity of $$O(1)$$ or $$O(\log Q)$$ per query.

In summary, the problem has been solved in a total of $$O(N + Q\log Q)$$ or $$O(Q\log Q)$$ time, the latter of which is independent of $$N$$.

Sample code (C++)

### Solution 2

For $$0 \leq h \lt N$$, consider incrementing $$h$$ one by one until it becomes $$A_{h \bmod N} = -1$$; let $$p(h)$$ be first such $$h \bmod N$$.

Prepare an auxiliary array $$P = (P_0, \dots, P_{N - 1})$$ initialized with $$P_h = h$$, which we use to find $$p(h)$$.

In order to find $$p(h)$$, we do as follows.

• While $$A_h \neq -1$$, repeat assigning $$h \leftarrow P_h$$.

Also, when updating an element of $$A_k = -1$$ with a value other than $$-1$$, we update as $$P_{k} \leftarrow p(k + 1)$$.

Did you recognize that the operations above are similar to the data structure called Union-Find? We can sue a method called coordinate compression to process each operation in amortized $$O(\log N)$$ time.

In summary, the problem has been solved in a total of $$O(N + Q\log N)$$ time.

Sample code (C++)

### By the way

This problem is based on Linear probing in Open addressing, which is a method of implementing Hash tables.
As we introduced in the “Naive solution” section, if the distribution of $$x_i \bmod N$$ is biased, then it may require more steps to process. In order to accomplish fast hash table, it is crucial to use a hash function that yields uniform values.

posted:
last update: