Set Merging

题意翻译

- 给定长度为 $n$ 的序列 $a$，最初有 $n$ 个集合 $\{a_1\},\{a_2\},\ldots,\{a_{n-1}\},\{a_n\}$。 - 接下来给定 $q$ 个询问，每次询问给出 $l,r$，你需要通过若干次操作制作出集合 $\{a_l,a_{l+1},\ldots,a_{r-1},a_r\}$。注意：操作过程中集合总数不能超过 $2.2\cdot 10^6$。 - 操作是指：你可以合并两个集合 $A,B$，但要满足 $\max\limits_{u\in A}u<\min\limits_{u\in B}u$。注意：合并后集合 $A,B$ **依然存在**。 - Translated by [Sept](/user/224931)

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

3 2
1 3 2
2 3
1 3

输出样例 #1

6
3 2
1 3
5 2
4 6

输入样例 #2

2 4
2 1
1 2
1 2
1 2
1 1

输出样例 #2

5
2 1
2 1
2 1
5 3 3 1

说明

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.