Set Merging
Contest: Codeforces Global Round 9
Difficulty rating: 3300
Tags: constructive algorithms, divide and conquer

You are given a permutation $$$a_1, a_2, \dots, a_n$$$ of numbers from $$$1$$$ to $$$n$$$. Also, you have $$$n$$$ sets $$$S_1,S_2,\dots, S_n$$$, where $$$S_i=\{a_i\}$$$. Lastly, you have a variable $$$cnt$$$, representing the current number of sets. Initially, $$$cnt = n$$$.

We define two kinds of functions on sets:

$$$f(S)=\min\limits_{u\in S} u$$$;

$$$g(S)=\max\limits_{u\in S} u$$$.

You can obtain a new set by merging two sets $$$A$$$ and $$$B$$$, if they satisfy $$$g(A)<f(B)$$$ (Notice that the old sets do not disappear).

Formally, you can perform the following sequence of operations:

- $$$cnt\gets cnt+1$$$;
- $$$S_{cnt}=S_u\cup S_v$$$, you are free to choose $$$u$$$ and $$$v$$$ for which $$$1\le u, v < cnt$$$ and which satisfy $$$g(S_u)<f(S_v)$$$.

You are required to obtain some specific sets.

There are $$$q$$$ requirements, each of which contains two integers $$$l_i$$$,$$$r_i$$$, which means that there must exist a set $$$S_{k_i}$$$ ($$$k_i$$$ is the ID of the set, you should determine it) which equals $$$\{a_u\mid l_i\leq u\leq r_i\}$$$, which is, the set consisting of all $$$a_i$$$ with indices between $$$l_i$$$ and $$$r_i$$$.

In the end you must ensure that $$$cnt\leq 2.2\times 10^6$$$. Note that you don't have to minimize $$$cnt$$$. It is guaranteed that a solution under given constraints exists.

Input format:
The first line contains two integers $$$n,q$$$ $$$(1\leq n \leq 2^{12},1 \leq q \leq 2^{16})$$$  — the length of the permutation and the number of needed sets correspondently.

The next line consists of $$$n$$$ integers $$$a_1,a_2,\cdots, a_n$$$ ($$$1\leq a_i\leq n$$$, $$$a_i$$$ are pairwise distinct)  — given permutation.

$$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i,r_i$$$ $$$(1\leq l_i\leq r_i\leq n)$$$, describing a requirement of the $$$i$$$-th set.

Output format:
It is guaranteed that a solution under given constraints exists.

The first line should contain one integer $$$cnt_E$$$ $$$(n\leq cnt_E\leq 2.2\times 10^6)$$$, representing the number of sets after all operations.

$$$cnt_E-n$$$ lines must follow, each line should contain two integers $$$u$$$, $$$v$$$ ($$$1\leq u, v\leq cnt'$$$, where $$$cnt'$$$ is the value of $$$cnt$$$ before this operation), meaning that you choose $$$S_u$$$, $$$S_v$$$ and perform a merging operation. In an operation, $$$g(S_u)<f(S_v)$$$ must be satisfied.

The last line should contain $$$q$$$ integers $$$k_1,k_2,\cdots,k_q$$$ $$$(1\leq k_i\leq cnt_E)$$$, representing that set $$$S_{k_i}$$$ is the $$$i$$$th required set.

Please notice the large amount of output.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample:

We have $$$S_1=\{1\},S_2=\{3\},S_3=\{2\}$$$ initially.

In the first operation, because $$$g(S_3)=2<f(S_2)=3$$$, we can merge $$$S_3,S_2$$$ into $$$S_4=\{2,3\}$$$.

In the second operation, because $$$g(S_1)=1<f(S_3)=2$$$, we can merge $$$S_1,S_3$$$ into $$$S_5=\{1,2\}$$$.

In the third operation, because $$$g(S_5)=2<f(S_2)=3$$$, we can merge $$$S_5,S_2$$$ into $$$S_6=\{1,2,3\}$$$.

For the first requirement, $$$S_4=\{2,3\}=\{a_2,a_3\}$$$, satisfies it, thus $$$k_1=4$$$.

For the second requirement, $$$S_6=\{1,2,3\}=\{a_1,a_2,a_3\}$$$, satisfies it, thus $$$k_2=6$$$

Notice that unused sets, identical sets, outputting the same set multiple times, and using sets that are present initially are all allowed.

Example input:
3 2
1 3 2
2 3
1 3

Example output:
6
3 2
1 3
5 2
4 6

Example input:
2 4
2 1
1 2
1 2
1 2
1 1

Example output:
5
2 1
2 1
2 1
5 3 3 1

Editorial:
First, two sets $$$a$$$ and $$$b$$$ can be merged if and only if the range of elements in $$$a$$$ do not intersect with the range of elements in $$$b$$$. It is obvious because if they intersect, neither $$$g(a)<f(b)$$$ nor $$$g(b)<f(a)$$$ are satisfied. If they do not intersect, there must be one of them satisfied.
Notice that $$$2\times n\sqrt{q}$$$ is near to $$$2.2\times 10^6$$$, this hints us to use sqrt-decomposition.
We separate the numbers $$$1,2,\cdots,n$$$ into $$$\dfrac{n}{S}$$$ consecutive blocks, each of size $$$S$$$.
Consider a block $$$B_i=[l,r]$$$, we take all elements in the original permutation that satisfy $$$l\leq a_i \leq r$$$, and form a new sequence that preserves the original order.
For example, if the permutation $$$9,8,2,1,5,6,3,7,4$$$ is divided into $$$3$$$ blocks $$$B_1=[1,3],B_2=[4,6],B_3=[7,9]$$$, their sequences will be $$$2,1,3$$$ and $$$5,6,4$$$ and $$$9,8,7$$$.
Consider any consecutive subsequence in the permutation. We want to construct a set that just contains all elements in it. We can first divide this subsequence into $$$\dfrac{n}S$$$ subsequences in each block that contains only elements in this block and merge them up.
For example, if we want the subsequence $$$8,2,1,5,6,3,7$$$ in the permutation above, then we can divide it into $$$2,1,3$$$ and $$$5,6$$$ and $$$8,7$$$.
Notice that those subsequences in each block are also consecutive subsequences. Also, notice that since the range of elements in each block do not intersect, the range of elements in these subsequences also do not intersect. This means that if we can somehow construct the set that equals the set of each of those subsequences, we can just merge those subsequences of each block to form the original subsequence that we want to obtain in $$$\dfrac{n}S-1$$$ merges.
Thus the process of constructing sets in total costs less that $$$\dfrac{qn}S$$$ merges.
Now we have to construct the subsequences of each block, notice that the subsequences are consecutive, thus we can just construct sets of all of those $$$\dfrac12S(S+1)$$$ consecutive subsequences.
Consider divide and conquer. We can divide a sequence in to two parts of equal size, construct subsequences of them, and try to merge them to obtain the new sets. So how do we split and merge?
Consider two sequences, that elements in the first sequence is less than elements in the second, and we have already constructed the sets of all the consecutive subsequences in each of those sequences. Now we consider a sequence that contains the union of the elements in the two subsequences. All elements in sequences here are ordered according to the order in the original permutation. Now we want to construct all the consecutive subsequences in the new sequence. Consider for each consecutive subsequence in the new sequence, it must be composed by two parts, the ones present in the first sequence, and the one present in the second. It is obvious that each part is also a consecutive subsequence in the respective sequence, thus the sets representing them is already constructed. Because the two sequence do not intersect in range of elements, we can just merge those two sets to form the new one.
For example, we want to obtain all subsequences of the sequence $$$1,4,3,2,6,5$$$, and we have already obtained the ones of $$$1,3,2$$$ and $$$4,6,5$$$.
So if we want to get the consecutive subsequence $$$1,4,3,2,6$$$, we first divide it into $$$1,3,2$$$ and $$$4,6$$$. Because the sets of them are already constructed(they are consecutive subsequences of $$$1,3,2$$$ and $$$4,6,5$$$), and their range of elements do not intersect, we can merge it in one operation.
Other consecutive subsequences can also be obtained similarly.
Thus there are $$$\dfrac12S(S+1)$$$ subsequences, and less than $$$\dfrac12S(S-1)$$$ need a merge operation (because those with only one element in it need no operation).
We use $$$f(S)$$$ to denote the number of operation needed to construct all consecutive subsequences of a block of length $$$S$$$
There is $$$f(1)=0$$$ and $$$f(x)\leq \dfrac12x^2+f(\lfloor x/2\rfloor)+f(\lceil x/2\rceil)$$$,(if we divide a subsequence evenly),it can be proved that $$$f(x)\leq x^2$$$
So, we need $$$\dfrac{n}S\times S^2$$$ operations to construct all consecutive subsequences.
So in total, $$$nS+\dfrac{nq}S$$$ operations are needed. According to the mean inequality, there is $$$nS+\dfrac{nq}S\geq 2\sqrt{n^2q}=2n\sqrt{q}$$$, and if $$$S=\sqrt{q}$$$, $$$nS+\dfrac{nq}S=2\sqrt{n^2q}=2n\sqrt{q}$$$
And, $$$2n\sqrt{q}\leq 2^{21}< 2.2\times 10^6$$$, thus the restriction is satisfied.
Also, there exists a solution based on segment-tree.
The main idea is to maintain a segment-tree of $$$1$$$ to $$$n$$$, in each node, we save a hash-map of sets with elements in the range of that node already constructed.
Anytime we want a new set, we do a query on the segment tree, if the set on that node is constructed, we return it. Otherwise, we split the wanted set into two parts, and query on its sons, and merge them.
The details is omitted due to laziness issue.
And we find that this solution can pass, why?
Suppose $$$n=2^N$$$ and $$$q=2^Q$$$
We can calculate that we need no more than
$$$$$$\sum_{i=0}^n 2^{N-i}\min(2^{2i-1},2^Q) $$$$$$
sets. This is because in the $$$i$$$th layer(bottom to top) of the segment-tree, there are $$$2^{N-i}$$$ nodes, each one can contain no more than $$$2^i(2^i-1)/2$$$ sets (the consecutive subsegment limitation). but it is also bounded by $$$2^Q$$$ queries, because a query can only visit a node at most once.
Calculating this sum yield a bound lower that the resiriction.
Also we can find that this solution is similar to the previous sol.
We find that
For $$$i \leq Q/2$$$,the sum is
$$$$$$\sum_{i=0}^{Q/2} 2^{N-i}2^{2i-1}= \sum_{i=0}^{Q/2} 2^{N+i-1}\leq 2^{N+Q/2} $$$$$$
And for $$$i> Q/2$$$ the sum is
$$$$$$2^Q \sum_{i=Q/2+1}^N 2^{N-i}\leq 2^Q 2^{N-Q/2}=2^{N+Q/2}$$$$$$
Summing these two parts yield $$$2^{N+Q/2+1}$$$ which is also $$$2n\sqrt{q}$$$
So these solutions have the same complexity.
Other than that, we observe that the lower-$$$Q/2$$$ layers is just like those blocks constructed in the first solution, only the merging in the upper one is different, the first solution used brute-force, while the second just extended the segment-tree up.
Thus, we say that the first solution is just the second one, but bounded manually. So these two solutions are intrinsically similar.