LIS Keeping Swaps

AtCoder

IDawtf2025_a

Time2000ms

Memory256MB

Difficulty—

You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$. You can perform the following operation zero or more times: * Choose an integer $i$ ($1 \leq i \leq N-1$) and swap the values of $P_i$ and $P_{i+1}$. Here, both of the following conditions must be satisfied: * $P_i>P_{i+1}$ holds immediately before the operation. * The operation does not change the length of the longest increasing subsequence of $P$. Find the lexicographically smallest permutation among all permutations that can be obtained as $P$ after operations. Solve $T$ test cases for each input. What is lexicographic order on sequences?A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is **lexicographically smaller** than a sequence $T = (T_1,T_2,\ldots,T_{|T|})$ if either of the following conditions 1. and 2. holds. Here, $|S|$ and $|T|$ represent the lengths of $S$ and $T$, respectively. 1. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. 2. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold: * $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$. * $S_i$ is (numerically) smaller than $T_i$. ## Constraints * $1 \leq T \leq 250000$ * $1 \leq N \leq 250000$ * $P$ is a permutation of $(1,2,\ldots,N)$. * The sum of $N$ over all test cases in each input does not exceed $250000$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each test case is given in the following format: $N$ $P_1$ $P_2$ $\cdots$ $P_N$ [samples]

Samples

Input #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

Output #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

Let us explain the first test case. For $P=(2,3,1)$, the operation cannot be performed with $i=1$, but can be performed with $i=2$. After the operation, $P=(2,1,3)$, and no further operations can be performed from here. Among the permutations reachable starting from $P=(2,3,1)$, the lexicographically smallest one is $(2,1,3)$.

API Response (JSON)

{
  "problem": {
    "name": "LIS Keeping Swaps",
    "description": {
      "content": "You are given a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$. You can perform the following operation zero or more times: *   Choose an integer $i$ ($1 \\leq i \\leq N-1$) and swap the valu",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "awtf2025_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$.\nYou can perform the following operation zero or more times:\n\n*   Choose an integer $i$ ($1 \\leq i \\leq N-1$) and swap the valu...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments