Range MEX queries offline in O(log n)

Revision en3, by one_autum_leaf, 2023-06-27 18:52:21

Consider the following problem : Your are given an array $$$a_1, a_2, ..., a_n$$$ and q queries of form $$$l r$$$. For each query you have to find the MEX of the array $$$a_l, a_{l+1}, ..., a_r$$$. The queries are offline. One approach to the problem is discussed here.

Tags mex, range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en19 English one_autum_leaf 2023-06-27 20:24:52 15 Tiny change: 'discussed [here](ht' -> 'discussed in the comment [here](ht'
en18 English one_autum_leaf 2023-06-27 20:24:09 30 (published)
en17 English one_autum_leaf 2023-06-27 20:22:14 26 Tiny change: ', 0]$.\n\n![ ](' -> ', 0]$.\n\nWe start at root node.\n\n![ ]('
en16 English one_autum_leaf 2023-06-27 20:21:28 41
en15 English one_autum_leaf 2023-06-27 20:19:03 2 Tiny change: 'dash; $O(nlog n + q(log ' -> 'dash; $O(n \log_n + q(log '
en14 English one_autum_leaf 2023-06-27 20:16:20 1 Tiny change: 'O(q log n). Updating' -> 'O(q log n)$. Updating'
en13 English one_autum_leaf 2023-06-27 20:15:42 253
en12 English one_autum_leaf 2023-06-27 20:12:53 15 Tiny change: 'array is $1, 0$.\n\n![ ]' -> 'array is $[a_2, a_3] = [1, 0]$.\n\n![ ]'
en11 English one_autum_leaf 2023-06-27 20:12:17 519 Tiny change: 'imgur.com/a/UkzuMa5)\n\n~~~~~' -> 'imgur.com/5TOuXF6)\n\n~~~~~'
en10 English one_autum_leaf 2023-06-27 20:02:50 35 Tiny change: '., a_r$.\n\n~~~~~\' -> '., a_r$.\n![ ](https://imgur.com/a/UkzuMa5)\n\n~~~~~\'
en9 English one_autum_leaf 2023-06-27 19:48:07 163
en8 English one_autum_leaf 2023-06-27 19:45:55 1610 Tiny change: 'egin{math}a_x = 1\end{math}\begin{math}a_x = 1\end{math}\begin{math}' -> 'egin{math}'
en7 English one_autum_leaf 2023-06-27 19:10:31 36
en6 English one_autum_leaf 2023-06-27 19:09:34 3 Tiny change: 'et $b_x = $ \bigl\{\n\n~~~~~\' -> 'et $b_x = \bigl\{ $\n\n~~~~~\'
en5 English one_autum_leaf 2023-06-27 19:09:15 199
en4 English one_autum_leaf 2023-06-27 19:00:34 1566
en3 English one_autum_leaf 2023-06-27 18:52:21 180
en2 English one_autum_leaf 2023-06-27 18:50:49 2 Tiny change: 'y $a_l, a_l+1, ..., a_r' -> 'y $a_l, a_{l+1}, ..., a_r'
en1 English one_autum_leaf 2023-06-27 18:50:11 222 Initial revision (saved to drafts)