Official
D - Kth Excluded Editorial by en_translator
Let us call an integer good if it is different from either of \(A_1, A_2, \dots, A_N\).
For each \(i\), find the number of good integers less than or equal to \(A_i\) and record them as \(C_i\).
Then, the \(K\)-th smallest good integer can be found as follows:
- If \(C_N < K\)
- The answer is always greater than \(A_N\). Since every integer greater than \(A_N\) is a good integer, the answer is \(A_N + (K - C_N)\).
- If \(C_N \geq K\)
- Find with binary search the minimum \(i\) such that \(C_i \geq K\), then the answer is greater than \(A_{i - 1}\) and less than \(A_i\) (where we assume \(A_0 = 0\)). Since every integer greater than \(A_{i - 1}\) and less than \(A_i\) is a good integer, the answer is \((A_i - 1) - (C_i - K)\), that is, \(C_i - K\) elements before \(A_{i} - 1\).
The complexity is \(O (N + Q \log N)\).
posted:
last update: