Range MEX queries offline in O(log n) - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

Range MEX queries offline in O(log n)

Revision en2, by one_autum_leaf, 2023-06-27 18:50:49

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$$$.

Tags

mex, range query

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en19		one_autum_leaf	2023-06-27 20:24:52	15	Tiny change: 'discussed [here](ht' -> 'discussed in the comment [here](ht'
	en18		one_autum_leaf	2023-06-27 20:24:09	30	(published)
	en17		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		one_autum_leaf	2023-06-27 20:21:28	41
	en15		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		one_autum_leaf	2023-06-27 20:16:20	1	Tiny change: 'O(q log n). Updating' -> 'O(q log n)$. Updating'
	en13		one_autum_leaf	2023-06-27 20:15:42	253
	en12		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		one_autum_leaf	2023-06-27 20:12:17	519	Tiny change: 'imgur.com/a/UkzuMa5)\n\n~~~~~' -> 'imgur.com/5TOuXF6)\n\n~~~~~'
	en10		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		one_autum_leaf	2023-06-27 19:48:07	163
	en8		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		one_autum_leaf	2023-06-27 19:10:31	36
	en6		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		one_autum_leaf	2023-06-27 19:09:15	199
	en4		one_autum_leaf	2023-06-27 19:00:34	1566
	en3		one_autum_leaf	2023-06-27 18:52:21	180
	en2		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		one_autum_leaf	2023-06-27 18:50:11	222	Initial revision (saved to drafts)