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.