MEX Interval Score

Call an interval $I=[l,r]$ a minimal MEX interval if no smaller nonempty subinterval of $I$ has the same MEX. Every interval of length $1$ is minimal.

All $C_i$ are nonnegative. If an endpoint can be removed without changing the MEX, removing it does not increase the cost sum. Repeating this operation produces a minimal MEX interval with the same MEX and a score no smaller than the original score. Therefore, only minimal MEX intervals can be optimal.

For a minimal interval $[l,r]$ of length at least $2$, we have $A_l\ne A_r$.

First suppose $A_l<A_r$. Removing the right endpoint must change the MEX, so

$$\operatorname{mex}(A_l,\cdots,A_r)>A_r.$$

For a fixed right endpoint $r$, there is a unique largest $l$ satisfying this condition. Let $\operatorname{last}_r(x)$ be the last occurrence of $x$ up to position $$. Then

$$l=\min_{0\le x\le A_r}\operatorname{last}_r(x).$$

All required values must exist, and the previous occurrence of $A_r$ must be before $l$ so that removing position $r$ changes the MEX.

The case $A_l>A_r$ is symmetric. Let $\operatorname{next}_l(x)$ be the first occurrence of at or after . Then the candidate endpoint is

$$r=\max_{0\le x\le A_l}\operatorname{next}_l(x),$$

and the next occurrence of $A_l$ must be after $r$.

The first case contributes at most one candidate for each $r$, and the second case contributes at most one candidate for each $l$. Together with all singleton intervals, there are only $O(N)$ candidates.

During a left-to-right scan, maintain the last occurrence of every value $0,1,\cdots,N$ in a segment tree. We need the minimum over a value prefix and the smallest value whose stored position is less than a given $l$; the latter is the interval MEX. A symmetric right-to-left scan maintains next occurrences. All minimal intervals are found in $O(N\log N)$ time.

For every candidate $[s,e]$, compute

$$w(s,e)=B_{\operatorname{mex}(A_s,\cdots,A_e)}-(P_e-P_{s-1}),$$

where $P$ is the prefix sum of $C$.

Sort queries by their right endpoint. Sort candidates by $e$ and add every candidate with $e$ not exceeding the current query endpoint. A segment tree indexed by $s$ stores the maximum weight added at each start position. The answer to query $[l,r]$ is the maximum over start positions $[l,N]$. Every added candidate already satisfies , so this is exactly the set of candidates contained in the query interval.

The total time complexity is $O((N+Q)\log N)$ and the memory complexity is $O(N+Q)$.