← 返回题目列表

Codeforces · 1579/E1

E1. 双端队列排列最小化

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

事实上,问题E1和E2并没有太多共同点。您可能应该将它们视为两个独立的问题。

给出了大小为 $$$n$$$ 的排列 $$$p$$$。大小为 $$$n$$$ 的排列是大小为 $$$n$$$ 的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好出现一次。例如,$$$[1, 4, 3, 2]$$$ 和 $$$[4, 2, 1, 3]$$$ 是正确的排列,而 $$$[1, 2, 4]$$$ 和 $$$[1, 2, 2]$$$ 则不是。

让我们考虑一个空的双端队列(双端队列)。双端队列是一种支持在开头和结尾添加元素的数据结构。因此,如果双端队列中当前有元素 $$$[1, 5, 2]$$$,则在开头添加元素 $$$4$$$ 将生成序列 $$$[\color{red}{4}, 1, 5, 2]$$$,在末尾添加相同元素将生成 $$$[1, 5, 2, \color{red}{4}]$$$。

排列的元素按顺序添加到最初为空的双端队列中,从 $$$p_1$$$ 开始,到 $$$p_n$$$ 结束。在将每个元素添加到双端队列之前,您可以选择是将其添加到开头还是末尾。

例如,如果我们考虑排列 $$$p = [3, 1, 2, 4]$$$,则可能的操作序列之一如下所示: $$$\quad$$$ 1. 将 $$$3$$$ 添加到双端队列的末尾:双端队列中有一个序列 $$$[\color{red}{3}]$$$ ;$$$\quad$$$ 2.add $$$1$$$ 到双端队列的开头:双端队列中有一个序列 $$$[\color{red}{1}, 3]$$$ ;$$$\quad$$$ 3. 将 $$$2$$$ 添加到双端队列的末尾:双端队列中有一个序列 $$$[1, 3, \color{red}{2}]$$$ ;$$$\quad$$$ 4. 添加 $$$4$$$ 到双端队列的末尾:双端队列中有一个序列 $$$[1, 3, 2, \color{red}{4}]$$$ ;

在处理整个排列后,找到双端队列中按字典顺序排列的最小可能元素序列。

如果存在 $$$i \leq n$$$ 使得 $$$x_1 = y_1$$$, $$$x_2 = y_2$$$、$$$\ldots$$$、$$$x_{i - 1} = y_{i - 1}$$$ 和 $$$x_i < y_i$$$。换句话说,如果序列 $$$x$$$ 和 $$$y$$$ 有一些(可能为空)匹配前缀,并且序列 $$$x$$$ 的下一个元素严格小于序列 $$$y$$$ 的相应元素。例如,序列 $$$[1, 3, 2, 4]$$$ 小于序列 $$$[1, 3, 4, 2]$$$,因为在开头的两个匹配元素 $$$[1, 3]$$$ 之后,第一个序列有一个元素 $$$2$$$,该元素小于第二个序列中的相应元素 $$$4$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列大小。描述的第二行包含 $$$n$$$ 以空格分隔的整数 $$$p_i$$$($$$1 \le p_i \le n$$$;所有 $$$p_i$$$ 都是唯一的)— 排列的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$t$$$ 行,每行包含相应测试用例的答案。测试用例的答案应包含 $$$n$$$ 以空格分隔的整数 - 执行所描述的算法后可以在双端队列中找到的按字典顺序排列的最小排列的元素。

示例

输入 #1

5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

输出 #1

1 3 2 4 
1 2 3 
1 3 2 
1 2 
1 2

注意

问题陈述中描述了从排列 $$$[3, 1, 2, 4]$$$ (第一个示例测试用例)中获取字典顺序最小排列 $$$[1, 3, 2, 4]$$$ 的方法之一。