CF1579E1 Permutation Minimization by Deque

实际上，问题 E1 和 E2 并没有太多共同之处。你应该将它们视为两个独立的问题。 给定一个长度为 $n$ 的排列 $p$。长度为 $n$ 的排列是一个长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。例如，$[1, 4, 3, 2]$ 和 $[4, 2, 1, 3]$ 是合法的排列，而 $[1, 2, 4]$ 和 $[1, 2, 2]$ 不是。 我们考虑一个初始为空的 [双端队列（deque）](https://tinyurl.com/pfeucbux)。双端队列是一种支持在队首和队尾都能添加元素的数据结构。例如，如果当前队列中的元素为 $[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]$，一种可能的操作序列如下： 1. 将 $3$ 加入队尾：队列为 $[\color{red}{3}]$； 2. 将 $1$ 加入队首：队列为 $[\color{red}{1}, 3]$； 3. 将 $2$ 加入队尾：队列为 $[1, 3, \color{red}{2}]$； 4. 将 $4$ 加入队尾：队列为 $[1, 3, 2, \color{red}{4}]$。 请你找出在整个排列处理完后，双端队列中可能得到的字典序最小的序列。 一个序列 $[x_1, x_2, \ldots, x_n]$ 的字典序小于序列 $[y_1, y_2, \ldots, y_n]$，当且仅当存在某个 $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$ 的对应元素小，则 $x$ 的字典序更小。例如，序列 $[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$ 个用空格分隔的整数，表示通过上述算法得到的字典序最小的排列。

从排列 $[3, 1, 2, 4]$ 得到字典序最小排列 $[1, 3, 2, 4]$ 的一种方式已在题目描述中给出。 由 ChatGPT 4.1 翻译