Contest Duration: - (local time) (100 minutes) Back to Home
Official

## F - Union of Two Sets Editorial by en_translator

This problem is inspired by a data structure called “Sparse Table.”

Hereinafter, for integers $$l$$ and $$r$$ such that $$l \leq r$$, let us call a set of integers between $$l$$ and $$r$$ (inclusive) by segment $$[l, r]$$. That is, $$[l, r] \coloneqq \lbrace l, l+1, l+2, \ldots, r\rbrace$$. Also, let us define the length of a segment $$[l, r]$$ by the size of the set, $$r-l+1$$.

In this problem, you are asked to choose $$M$$ segments beforehand so that you can represent any segment $$[L, R]$$ that is a subset of $$[1, N]$$ as a union of two of the chosen segments.

To come to the point, it is sufficient to choose all the following elements:

• Every segment of length $$1$$ that is a subsets of $$[1, N]$$
• Every segment of length $$2$$ that is a subsets of $$[1, N]$$
• Every segment of length $$4$$ that is a subsets of $$[1, N]$$
• $$\cdots$$
• Every segment of length $$$2^{\lfloor \log_2 N \rfloor}$$$$that is a subsets of$$[1, N]$.

For example, if $$N = 10$$, we choose the following $$29$$ segments:

• $$10$$ segments of length $$1$$: $$[1, 1], [2, 2], \ldots, [10, 10]$$.
• $$9$$ segments of length $$2$$: $$[1, 2], [2, 3], \ldots, [9, 10]$$.
• $$4$$ segments of length $$4$$: $$[1, 4], [2, 5], \ldots, [7, 10]$$.
• $$3$$ segments of length $$8$$: $$[1, 8], [2, 9], \ldots, [3, 10]$$.

In this choice, there are at most $$N$$ segments of each length, and there are $$\lfloor \log_2 N \rfloor + 1$$ kinds of distinct lengths, so $$M \leq N(\lfloor \log_2 N \rfloor + 1)$$. Even in the maximum case $$N = 4000$$, we have $$M \leq 4000 \times (\lfloor \log_2 4000 \rfloor + 1) = 48000$$, which is below the upper bound $$50000$$.

Also, given a segment $$[L, R]$$ as a query, we can represent it as a union of two of the chosen segments, segment $$[L, L+2^K-1]$$ and $$[R-2^K+1, R]$$, where $$K$$ is the maximum integer such that $$2^K \leq R-L+1$$.

Hence, by choosing the $$M$$ segments as described above, you can solve this problem.

Let me briefly introduce about the original idea, sparse table.

A sparse table is a data structure that, given a fixed array $$A$$ of length $$N$$, enables us to find the minimum value $$\min_{i \in [L, R]} A[i]$$ in a segment $$[L, R]$$ in an $$O(1)$$ time.

We achieve it by precalculating the minimum value of $$A$$ within each of the segments of $$[1, N]$$ whose length is $$1, 2, 4, \ldots, 2^{\lfloor \log_2 N \rfloor}$$ (there are $$O(N \log N)$$ such segments) as described in the editorial above.

Then, one can obtain the minimum value of $$A$$ within a segment $$[L, R]$$ by decomposing $$[L, R]$$ into the union of $$[L, L+2^K-1]$$ and $$[R-2^K+1, R]$$, then finding the smaller of the minimum value within $$[L, L+2^K-1]$$ and within $$[R-2^K+1, R]$$.

Since the minimum value within the segment $$[L, L+2^k-1]$$ can be found as the smaller of the minimum values within the segment $$[L, L+2^{k-1}-1]$$ and the segment $$[L+2^{k-1}, L+2^k-1]$$, one can complete the precalculation by filling the table in ascending order of $$k$$ in a total of $$O(N \log N)$$ time.

This data structure not only supports minimum values, but also other operations like maximum value, bitwise logical sums or products, and greatest common divisor. There is a refined variant of the sparse table, which is called a disjoint sparse table. If you are interested, take a look a it.

posted:
last update: