← 返回题目列表

Codeforces · 1375/H

H. 设置合并

中文机器翻译题面 查看原题

您将获得从 $$$1$$$ 到 $$$n$$$ 的数字排列 $$$a_1, a_2, \dots, a_n$$$。另外,您有 $$$n$$$ 集 $$$S_1,S_2,\dots, S_n$$$,其中 $$$S_i=\{a_i\}$$$。最后,您有一个变量 $$$cnt$$$,表示当前的集合数。最初,$$$cnt = n$$$。

我们在集合上定义两种函数:

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

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

如果满足$$$g(A)<f(B)$$$,则可以通过合并两个集合$$$A$$$和$$$B$$$来获得新集合(注意旧集合不会消失)。

正式而言,您可以执行以下操作序列:

- $$$cnt\获取cnt+1$$$;
- $$$S_{cnt}=S_u\cup S_v$$$,您可以自由选择 $$$u$$$ 和 $$$v$$$,其中 $$$1\le u, v < cnt$$$ 且满足 $$$g(S_u)<f(S_v)$$$。

您需要获得一些特定的套装。

有$$$q$$$要求,每个要求包含两个整数$$$l_i$$$,$$$r_i$$$,这意味着必须存在一个集合$$$S_{k_i}$$$($$$k_i$$$是集合的ID,你应该确定它)等于$$$\{a_u\mid l_i\leq u\leq r_i\}$$$,即由索引在 $$$l_i$$$ 和 $$$r_i$$$ 之间的所有 $$$a_i$$$ 组成的集合。

最后你必须确保$$$cnt\leq 2.2\times 10^6$$$。请注意,您不必最小化 $$$cnt$$$。保证在给定约束下存在解决方案。

输入

第一行包含两个整数 $$$n,q$$$ $$$(1\leq n \leq 2^{12},1 \leq q \leq 2^{16})$$$ — 排列的长度和相应的所需集合的数量。

下一行由 $$$n$$$ 整数 $$$a_1,a_2,\cdots, a_n$$$ ($$$1\leq a_i\leq n$$$, $$$a_i$$$ 成对不同) — 给定排列组成。

接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i,r_i$$$ $$$(1\leq l_i\leq r_i\leq n)$$$,描述第 $$$i$$$ 组的要求。

输出

保证在给定约束下存在解。

第一行应包含一个整数$$$cnt_E$$$ $$$(n\leq cnt_E\leq 2.2\times 10^6)$$$,表示所有操作后的集合数。

$$$cnt_E-n$$$ 行必须跟随,每行应包含两个整数 $$$u$$$、$$$v$$$($$$1\leq u, v\leq cnt'$$$,其中 $$$cnt'$$$ 是此操作之前 $$$cnt$$$ 的值),表示您选择 $$$S_u$$$, $$$S_v$$$ 并执行合并操作。在运算中,必须满足$$$g(S_u)<f(S_v)$$$。

最后一行应包含 $$$q$$$ 整数 $$$k_1,k_2,\cdots,k_q$$$ $$$(1\leq k_i\leq cnt_E)$$$,表示集合 $$$S_{k_i}$$$ 是第 $$$i$$$ 个所需集合。

请注意大量输出。

示例

输入 #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

注意

在第一个示例中:

我们最初有 $$$S_1=\{1\},S_2=\{3\},S_3=\{2\}$$$。

在第一个操作中,因为 $$$g(S_3)=2<f(S_2)=3$$$,我们可以将 $$$S_3,S_2$$$ 合并到 $$$S_4=\{2,3\}$$$ 中。

在第二个操作中,因为 $$$g(S_1)=1<f(S_3)=2$$$,我们可以将 $$$S_1,S_3$$$ 合并到 $$$S_5=\{1,2\}$$$ 中。

在第三个操作中,因为$$$g(S_5)=2<f(S_2)=3$$$,我们可以将$$$S_5,S_2$$$合并到$$$S_6=\{1,2,3\}$$$中。

对于第一个要求,$$$S_4=\{2,3\}=\{a_2,a_3\}$$$满足它,因此$$$k_1=4$$$。

对于第二个要求,$$$S_6=\{1,2,3\}=\{a_1,a_2,a_3\}$$$满足,因此$$$k_2=6$$$

请注意,未使用的集合、相同的集合、多次输出相同的集合以及使用最初存在的集合都是允许的。