Yet Another MEX Problem

The Key Lie to Stop Believing

The obvious-looking route is: “for every suffix, maintain its MEX, then count bigger elements.” That path is pain. Don’t do that.

Instead, define for any subarray $b$ and any value $x$ missing from $b$:

$$g(b,x)=\#\{j:b_j>x\}.$$

The weight of $b$ is

$$g(b,\operatorname{mex}(b)).$$

Now here is the whole trick: among all missing values $x$, the best one is always the MEX.

Why? If $x$ is missing, then by definition

$$\operatorname{mex}(b)\le x.$$

So every element greater than $x$ is also greater than $\operatorname{mex}(b)$, meaning

$$g(b,x)\le g(b,\operatorname{mex}(b)).$$

Since the MEX itself is missing, we get:

$$w(b)=\max_{x\notin b} g(b,x).$$

So we can stop explicitly tracking MEX. Huge win.

Fix the Right Endpoint

We need the answer for every right endpoint $r$:

$$\max_{1\le l\le r} w(a_l,\dots,a_r).$$

Using the rewrite above, this becomes:

$$\max_x \max_{l: x\notin a_l,\dots,a_r} \#\{j\in[l,r]:a_j>x\}.$$

Now fix some value $x$.

Let $last[x]$ be the last position where $x$ appears among $a_1,\dots,a_r$. If $x$ never appeared, set $last[x]=0$.

For $x$ to be missing from $a_l,\dots,a_r$, we must have

$$l>last[x].$$

Among all such $l$, which one maximizes the count of elements greater than $x$?

The earliest one:

$$l=last[x]+1.$$

Because moving $l$ to the right only deletes elements. Deleted elements might be useless, but they might also be greater than $x$; either way, the count cannot increase. So for each $x$, the best subarray ending at $r$ with $x$ missing is forced:

$$[last[x]+1,r].$$

Define

$$f[x]=\#\{j\in(last[x],r]:a_j>x\}.$$

Then the answer for right endpoint $r$ is simply

$$\max_{0\le x\le n} f[x].$$

That’s the entire problem. Everything else is just maintaining this array without doing dumb $O(n^2)$ stuff.

Updating $f$ When We Append a Value

Suppose we process the array left to right, and the new value is

$$y=a_r.$$

What happens to $f[x]$?

For $x<y$, the new element satisfies $y>x$, so it contributes $+1$ to $f[x]$.

For $x>y$, the new element does not satisfy $y>x$, so $f[x]$ does not change.

For $x=y$, the new element is an occurrence of $x$ itself. That means $last[x]$ becomes $r$, so the interval $(last[x],r]$ becomes empty. Therefore:

$$f[y]=0.$$

So every step does exactly this:

1. Add $1$ to every $f[x]$ with $0\le x<y$.
2. Set $f[y]=0$.
3. Output $\max_x f[x]$.

That is screaming “lazy segment tree”: range add, point assign, global max.

Why Values Only Go From $0$ to $n$

The array values satisfy $0\le a_i\le n$.

For any subarray of length at most $n$, its MEX is at most $n$. So tracking $x=0,1,\dots,n$ is enough.

The value $x=n$ is useful as a harmless sentinel. It never gets positive contribution from any element, since no array value is greater than $n$, but it keeps the indexing clean.

Correctness Proof

We prove that the algorithm outputs the required value for every right endpoint $r$.

First, for any subarray $b$, its weight equals

$$\max_{x\notin b} \#\{j:b_j>x\}.$$

The MEX is missing, so the maximum is at least the weight. For any other missing $x$, we have $\operatorname{mex}(b)\le x$, so the number of elements greater than $x$ is at most the number of elements greater than the MEX. Thus the maximum is exactly the weight.

Now fix a right endpoint $r$ and a value $x$. A subarray ending at $r$ has $x$ missing iff its left endpoint $l$ satisfies $l>last[x]$. Among all such $l$, choosing $l=last[x]+1$ maximizes the number of elements greater than $x$, because it includes every possible element that could contribute. Therefore the best value for this fixed $x$ is exactly

$$f[x]=\#\{j\in(last[x],r]:a_j>x\}.$$

Taking the maximum over all $x$ gives the best weight among all subarrays ending at $r$.

Finally, the update rules maintain these $f[x]$ values exactly. When $y=a_r$ arrives, it contributes to precisely those $x<y$. For $x=y$, the latest occurrence moves to $r$, so $f[y]$ becomes $0$. For $x>y$, nothing changes. Thus after each update, the segment tree stores the correct $f[x]$ values, and its maximum is the required answer.

Complexity

Each element causes one range add, one point assignment, and one global maximum query.

So the complexity is

$$O(n\log n)$$

per test case, with $O(n)$ memory. Clean, fast, no MEX gymnastics circus.