Prefix MEX#12785

Prefix MEX (Editorial)

Problem author:	Maryan Shyika
Prepared by:	Maryan Shyika
Tutorial:	Maryan Shyika

Idea

Let

b = [a_{L}, a_{L + 1}, \dots, a_{R}] .

b=[a_L,a_{L+1},\ldots,a_R].

For convenience, convert the query range $[l, r]$ [l,r] into coordinates of the original array:

X = L + l - 1, Y = L + r - 1.

X=L+l-1,\qquad Y=L+r-1.

We consider the cases $k = 1$ k=1, $k = 2$ k=2, and $k \geq 3$ k\ge 3 separately.

$k = 1$ k=1

For the current value of $L$ , maintain the array

c_{i} = f ([a_{L}, a_{L + 1}, \dots, a_{i}]) .

c_i=f([a_L,a_{L+1},\ldots,a_i]).

For $L = 1$ L=1, this array can be built with a standard left-to-right scan while maintaining the current MEX.

Now consider the transition from $L$ to $L + 1$ L+1. Let

v = a_{L} .

v=a_L.

Let $p$ be the next position after $L$ where the value $v$ occurs. If there is no such position, set $p = n + 1$ p=n+1.

After removing $a_{L}$ a_L, prefix MEX values may change only before the next occurrence of $v$ , that is, up to position $p - 1$ p-1.

Let $x$ be the first position such that

c_{x} > v .

c_x>v.

Then after moving to $L + 1$ L+1, the new prefix MEX on the whole segment

[x, p - 1]

[x,p-1]

becomes equal to $v$ . Therefore, we need to perform

c_{i} = v

c_i=v

for all $i \in [x, p - 1]$ i\in[x,p-1].

To maintain the array $c$ , we use a segment tree supporting:

range assignment;
range sum;
finding the first position $x$ such that $c_{x} > v$ c_x>v.

Then the answer to a query with $k = 1$ k=1 is

i = X \sum Y c_{i} .

\sum_{i=X}^{Y}c_i.

$k = 2$ k=2

Let

d = f (c) .

d=f(c).

Since the array $c$ is nondecreasing, the value of $d$ increases by one whenever the next required value

0, 1, 2, \dots

0,1,2,\ldots

appears in $c$ for the first time.

Let $p_{x}$ p_x be the first position where the value $x$ occurs in $c$ .

The value $x$ affects the answer only if the first occurrences form the chain

p_{0} < p_{1} < \dots < p_{x} .

p_0<p_1<\ldots<p_x.

In this case, the appearance of $x$ increases the prefix MEX at every position starting from $p_{x}$ p_x. Therefore, it corresponds to the operation

d_{i} \leftarrow d_{i} + 1

d_i\gets d_i+1

for all

i \in [p_{x}, n] .

i\in[p_x,n].

Thus, the array $d$ can be maintained using a second segment tree that supports range addition and range sum queries.

When moving from $L$ to $L + 1$ L+1, the structure of first occurrences changes, and therefore the initial strictly increasing chain

p_{0} < p_{1} < p_{2} < \dots

p_0<p_1<p_2<\ldots

may also change.

If some values become part of this chain, we apply

[p_{x}, n] \leftarrow + 1.

[p_x,n]\gets +1.

If some values stop being part of the chain, we apply

[p_{x}, n] \leftarrow - 1.

[p_x,n]\gets -1.

These changes can be maintained amortized, so the total number of updates over the whole sweep over $L$ is linear.

Then the answer to a query with $k = 2$ k=2 is

i = X \sum Y d_{i} .

\sum_{i=X}^{Y}d_i.

$k \geq 3$ k\ge 3

After the third application of $f$ , the array is guaranteed to become constant.

If $a_{L} = 0$ a_L=0, then the first element of $f (b)$ is equal to $1$ , so $f (b)$ contains no zero. Therefore,

f^{2} (b) = [0, 0, \dots, 0],

f^2(b)=[0,0,\ldots,0],

and

f^{3} (b) = [1, 1, \dots, 1] .

f^3(b)=[1,1,\ldots,1].

If $a_{L} \neq = 0$ a_L\ne0, then the first element of $f (b)$ is equal to $0$ . After one more application of $f$ , every element of the resulting array is positive, so

f^{3} (b) = [0, 0, \dots, 0] .

f^3(b)=[0,0,\ldots,0].

After that, every further application of $f$ simply alternates between a constant array of zeros and a constant array of ones.

Therefore, for $k \geq 3$ k\ge3,

g (k, b) = [1, 1, \dots, 1]

g(k,b)=[1,1,\ldots,1]

if and only if

(a_{L} = 0) XOR (k mod 2 = 0) .

(a_L=0)\mathbin{\mathrm{XOR}}(k\bmod 2=0).

Otherwise,

g (k, b) = [0, 0, \dots, 0] .

g(k,b)=[0,0,\ldots,0].

Hence, the answer to a query with $k \geq 3$ k\ge3 is either

r - l + 1,

r-l+1,

or $0$ .

Complexity

We process values of $L$ sequentially from $1$ to $n$ .

For $k = 1$ k=1, each transition takes $O (lo g n)$ O(\log n).

For $k = 2$ k=2, each segment tree update takes $O (lo g n)$ O(\log n), while the total number of required changes is linear amortized.

Each query with $k = 1$ k=1 or $k = 2$ k=2 is answered in $O (lo g n)$ O(\log n), while a query with $k \geq 3$ k\ge3 is answered in $O (1)$ .

Therefore, the overall time complexity is $O ((n + q) lo g n)$ O((n+q)\log n).

The memory complexity is $O (n + q)$ O(n+q).

b = [a_{L}, a_{L + 1}, \dots, a_{R}] .

[l, r]

X = L + l - 1, Y = L + r - 1.

k = 1

k = 2

k \geq 3

k = 1

c_{i} = f ([a_{L}, a_{L + 1}, \dots, a_{i}]) .

L = 1

L + 1

v = a_{L} .

p = n + 1

a_{L}

p - 1

c_{x} > v .

L + 1

[x, p - 1]

c_{i} = v

i \in [x, p - 1]

c_{x} > v

k = 1

i = X \sum Y c_{i} .

k = 2

d = f (c) .

0, 1, 2, \dots

p_{x}

p_{0} < p_{1} < \dots < p_{x} .

p_{x}

d_{i} \leftarrow d_{i} + 1

i \in [p_{x}, n] .

L + 1

p_{0} < p_{1} < p_{2} < \dots

[p_{x}, n] \leftarrow + 1.

[p_{x}, n] \leftarrow - 1.

k = 2

i = X \sum Y d_{i} .

k \geq 3

a_{L} = 0

f^{2} (b) = [0, 0, \dots, 0],

f^{3} (b) = [1, 1, \dots, 1] .

a_{L} \neq = 0

f^{3} (b) = [0, 0, \dots, 0] .

k \geq 3

g (k, b) = [1, 1, \dots, 1]

(a_{L} = 0) XOR (k mod 2 = 0) .

g (k, b) = [0, 0, \dots, 0] .

k \geq 3

r - l + 1,

k = 1

O (lo g n)

k = 2

O (lo g n)

k = 1

k = 2

O (lo g n)

k \geq 3

O ((n + q) lo g n)

O (n + q)