← 返回题目列表

AtCoder · awtf2025_a

A. LIS 保留掉期

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

分数: 800 点

问题陈述

给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

您可以执行以下操作零次或多次:

  • 选择一个整数 i (1 \leq i \leq N-1)并交换值 P_i 和 P_{i+1}。 这里,必须满足以下两个条件:
    • P_i>P_{i+1} 在操作之前立即保持。
    • 该操作不会改变最长递增子序列的长度 P.

找到所有排列中按字典顺序排列的最小排列,可以通过以下方式获得 P 操作后。

解决 T 每个输入的测试用例。

序列的字典顺序是什么?

一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 如果以下条件 1. 和 2. 之一成立。 在这里, |S| 和 |T| 代表的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 存在一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
    • S_i (在数值上)小于 T_i.

约束

  • 1 \leq T \leq 250000
  • 1 \leq N \leq 250000
  • P 是一个排列 (1,2,\ldots,N).
  • 总和 N 每个输入中的所有测试用例不超过 250000.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N
P_1 P_2 \cdots P_N

输出

对于每个测试用例,输出答案。


示例输入 1

4
3
2 3 1
3
3 2 1
7
5 7 6 4 2 3 1
15
6 4 5 14 15 1 3 9 12 8 10 2 7 13 11

示例输出 1

2 1 3
3 2 1
5 2 1 7 6 4 3
4 1 6 5 3 2 9 8 7 14 12 10 15 13 11

让我们解释一下第一个测试用例。 对于 P=(2,3,1),无法执行该操作 i=1,但可以执行 i=2。 手术后, P=(2,1,3),并且无法从这里执行进一步的操作。 在可到达的排列中,从 P=(2,3,1),字典顺序最小的一个是 (2,1,3).