Bitwise Subsegment Exclusion#13086

Bitwise Subsegment Exclusion (Editorial)

Observation 1: Values of different lengths

Consider a binary sequence $b$ of length $k$ .

Its value is

v a l (b) = 2^{k} + i = 1 \sum k b_{i} \cdot 2^{k - i} .

val(b)=2^k+\sum_{i=1}^{k} b_i\cdot 2^{k-i}.

Therefore, every binary sequence of length $k$ has a value in the range

[2^{k}, 2^{k + 1} - 1] .

[2^k,2^{k+1}-1].

Moreover, every integer in this range corresponds to exactly one binary sequence of length $k$ .

For example:

sequences of length $1$ correspond to values $2, 3$ ;
sequences of length $2$ correspond to values $4, 5, 6, 7$ 4,5,6,7;
sequences of length $3$ correspond to values $8, \dots, 15$ 8,\dots,15.

So the problem is equivalent to finding the smallest integer $v \geq 2$ v\ge 2 whose corresponding binary sequence does not occur as a contiguous subsegment of the query range.

In other words, we need the MEX of the values of all subsegments inside $[l, r]$ [l,r], starting from $2$ .

Observation 2: We only need subsegments of length at most 18

There are

2^{18} = 262144

2^{18}=262144

different binary sequences of length $18$ .

Consider a query whose length is $m \leq 200000$ m\le 200000.

The number of contiguous subsegments of length $18$ inside it is at most

max (0, m - 17) \leq 199983.

\max(0,m-17)\le 199983.

Since

199983 < 262144,

199983 < 262144,

it is impossible for all binary sequences of length $18$ to appear.

Therefore, at least one binary sequence of length $18$ is always missing.

Hence the answer always has length at most $18$ , and therefore

answer \leq 2^{19} - 1 = 524287.

\text{answer}\le 2^{19}-1=524287.

So it is enough to consider only subsegments of lengths from $1$ to $18$ .

Observation 3: Process queries offline

Suppose we fix the left border $L$ .

For every value $v$ , define $b es t [v]$ as the minimum ending position of an occurrence of $v$ whose starting position is at least $L$ .

If no such occurrence exists, let

b es t [v] = + \infty.

best[v]=+\infty.

Now consider a query $[L, R]$ .

A value $v$ appears completely inside this query if and only if

b es t [v] \leq R .

best[v]\le R.

Indeed, $b es t [v]$ represents the earliest ending position among all occurrences starting at or after $L$ .

Therefore,

v is missing from [L, R] ⟺ b es t [v] > R .

v\text{ is missing from }[L,R] \iff best[v]>R.

This gives us an offline solution.

Sort all queries by decreasing $l$ .

We maintain a pointer $L$ , initially equal to $n + 1$ n+1, and move it from right to left.

Whenever we move from $L + 1$ L+1 to $L$ , we add every subsegment starting at position $L$ whose length is at most $18$ .

There are at most $18$ such subsegments.

For each one, suppose its length is $k$ and its binary part has value $x$ .

Its complete value is

v = 2^{k} + x .

v=2^k+x.

If the subsegment ends at position $R^{'}$ R', we update

b es t [v] = min (b es t [v], R^{'}) .

best[v]=\min(best[v],R').

How do we find the smallest missing value quickly?

For a query $[l, r]$ [l,r], we need the smallest $v$ such that

b es t [v] > r .

best[v]>r.

We build a segment tree over all possible values.

Each leaf corresponding to value $v$ stores $b es t [v]$ .

For every segment-tree node, we store the maximum $b es t [v]$ inside its interval.

Consider some segment of values.

There exists a missing value inside this segment if and only if at least one of its values satisfies

b es t [v] > r .

best[v]>r.

This is equivalent to saying

max b es t [v] > r .

\max best[v]>r.

Therefore, while searching for the answer:

if the maximum value stored in the left child is greater than $r$ , then the left child contains a missing value, so we move left;
otherwise, every value in the left child appears inside the query, so we move right.

When we reach a leaf, its index is exactly the smallest missing value.

Correctness Proof

We prove that the algorithm returns the correct answer for every query $[l, r]$ [l,r].

After the sweep reaches $L = l$ L=l, we have processed exactly all starting positions $s \geq l$ s\ge l.

For every value $v$ , $b es t [v]$ is therefore the minimum ending position among all occurrences of $v$ starting at some position $s \geq l$ s\ge l.

Thus, $v$ occurs completely inside $[l, r]$ [l,r] if and only if

b es t [v] \leq r .

best[v]\le r.

Consequently, $v$ is missing if and only if

b es t [v] > r .

best[v]>r.

The segment tree stores the maximum $b es t [v]$ in every interval.

Hence an interval contains at least one missing value if and only if its stored maximum is greater than $r$ .

During the segment-tree walk, we always move to the left child whenever it contains a missing value. Otherwise, we move to the right child.

Therefore, the reached leaf is the smallest value $v$ satisfying $b es t [v] > r$ best[v]>r, which is exactly the required minimum missing value.

Thus, the algorithm is correct.

Complexity

For every array position, we process at most $18$ subsegments.

Therefore, the total number of segment-tree updates is

O (18 n) .

Each update takes $O (lo g V)$ O(\log V), where

V = 2^{19} .

V=2^{19}.

Each query also performs one segment-tree walk in $O (lo g V)$ O(\log V).

Thus, the total time complexity is

O ((18 n + q) lo g V) .

O((18n+q)\log V).

The memory complexity is

O (V) .

Since $V = 2^{19}$ V=2^{19}, this easily fits the limits.

Implementation detail

It is completely fine to use a fixed segment-tree range up to $2^{19} - 1$ 2^{19}-1.

The implementation may also use

min (2^{19}, 4 n + 20)

\min(2^{19},4n+20)

as the upper bound.

This is safe as well.

Suppose the answer has length $k$ . Then every binary sequence of length $k - 1$ k-1 must already occur, otherwise a smaller value would be missing.

There are $2^{k - 1}$ 2^{k-1} such sequences, so necessarily

v a l (b) = 2^{k} + i = 1 \sum k b_{i} \cdot 2^{k - i} .

[2^{k}, 2^{k + 1} - 1] .

4, 5, 6, 7

8, \dots, 15

v \geq 2

[l, r]

2^{18} = 262144

m \leq 200000

max (0, m - 17) \leq 199983.

199983 < 262144,

answer \leq 2^{19} - 1 = 524287.

b es t [v] = + \infty.

b es t [v] \leq R .

v is missing from [L, R] ⟺ b es t [v] > R .

n + 1

L + 1

v = 2^{k} + x .

R^{'}

b es t [v] = min (b es t [v], R^{'}) .

[l, r]

b es t [v] > r .

b es t [v] > r .

max b es t [v] > r .

[l, r]

L = l

s \geq l

s \geq l

[l, r]

b es t [v] \leq r .

b es t [v] > r .

b es t [v] > r

O (lo g V)

V = 2^{19} .

O (lo g V)

O ((18 n + q) lo g V) .

V = 2^{19}

2^{19} - 1

min (2^{19}, 4 n + 20)

k - 1

2^{k - 1}