Meximum Array 2

The trick is to stop treating the queries like separate little puzzles. They share positions, so trying to satisfy each range independently gets messy fast. Instead, classify positions by what they are forced to be.

What min = k really says

For a constraint $(1,l,r)$, we need:

• every value in $[l,r]$ is at least $k$;
• at least one value in $[l,r]$ is exactly $k$.

So first mark every position that appears in at least one type-1 range. Call these positions forced-high.

Any forced-high position must be $\ge k$ in every valid array. That means it can never be one of $0,1,\dots,k-1$.

What MEX = k really says

For a constraint $(2,l,r)$, the segment must:

• contain every value $0,1,\dots,k-1$;
• contain no value equal to $k$.

Values bigger than $k$ are harmless. They are basically decorative junk food: allowed, but not useful.

Now combine this with forced-high positions. If a forced-high position lies inside a MEX range, it cannot help provide $0,1,\dots,k-1$, because it must be $\ge k$. Also, it cannot be exactly $k$, because MEX-$k$ ranges must not contain $k$. So such a position should just be $k+1$.

The main construction

Mark two things:

• high[i]: position $i$ belongs to some type-1 range;
• in_mex[i]: position $i$ belongs to some type-2 range.

Now assign values like this:

1. If high[i] is false, put values cyclically by the order of unmarked positions: $0,1,\dots,k-1,0,1,\dots$
2. If high[i] is true and in_mex[i] is true, set $a_i=k+1$.
3. If high[i] is true and in_mex[i] is false, set $a_i=k$.

That's the whole thing. Very 1400-ish: once you see the classification, the monster was cardboard.

Why every MEX constraint works

Take any type-2 interval $[l,r]$.

First, it contains no $k$:

• unmarked positions get values from $0$ to $k-1$;
• marked positions inside this MEX interval have in_mex = true, so they get $k+1$.

So $k$ is absent.

Now we need all values $0,1,\dots,k-1$ to appear.

Because the input is guaranteed valid, this interval must be able to contain those $k$ values somehow. But forced-high positions cannot hold values below $k$. Therefore, in any valid array, the values $0,1,\dots,k-1$ must all be placed on unmarked positions inside $[l,r]$. That requires at least $k$ unmarked positions in the interval.

Look at the global list of all unmarked positions from left to right. The unmarked positions inside any interval $[l,r]$ form a consecutive chunk of this list. We colored that list cyclically modulo $k$. Any consecutive chunk of length at least $k$ contains every residue $0,1,\dots,k-1$.

So every MEX range gets all small values and no $k$. Done.

Why every minimum constraint works

Take any type-1 interval $[l,r]$.

Every position in this interval was marked high, so every assigned value there is either $k$ or $k+1$. Therefore the minimum is at least $k$.

We still need the minimum to be exactly $k$, not $k+1$ everywhere.

Suppose this interval had no position outside all MEX constraints. Then every position in it would belong to some type-2 interval. But a type-1 interval needs at least one position equal to $k$, while any position inside a type-2 interval is forbidden from being $k$. Contradiction. Since the statement guarantees a valid array exists, every type-1 interval has at least one marked position not inside any MEX interval.

Our construction assigns exactly $k$ to all such positions. So the minimum is exactly $k$.

Complexity

We mark intervals directly. With $n,q \le 100$, this is tiny:

$O(nq)$

per test case, with $O(n)$ memory.