No.2665 Minimize Inversions of Deque
Problem Statement
You are given a permutation $P=(P_1,P_2,\ldots,P_n)$ of $(1,2,\ldots,n)$.
The sequence $A$ is initially empty, and you perform the following operation in the order $i=1,2,\ldots,n$.
- Add $P_i$ to the front or the back of $A$.
Find the minimum possible inversion number of $A$ after all operations have been performed.
Also, find the lexicographically smallest $A$ among those that achieve the minimum inversion number.
In $1$ file, $T$ test cases are given; solve the above problem for all of them.
Definition of inversion number
The inversion number of a sequence $X=(X_1,X_2,\ldots,X_m)$ is the number of integer pairs $(i,j)$ satisfying $1\leq i\lt j\leq m$ and $X_i\gt X_j$.Definition of lexicographic order
For sequences $X=(X_1,X_2,\ldots,X_m),\ Y=(Y_1,Y_2,\ldots,Y_m)$, if $X\neq Y$, there exists a unique $i\in\lbrace 1,2,\ldots,m\rbrace$ satisfying the following $2$ conditions.- $X_j=Y_j$ for every positive integer $j$ less than $i$
- $X_i\neq Y_i$
For such $i$, $X$ is said to be lexicographically smaller than $Y$ if and only if $X_i\lt Y_i$.
Input
The input is given from Standard Input in the following format.
$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$
Here, for $i=1,2,\ldots,T$, $\mathrm{testcase}_i$ represents the $i$-th test case and is given in the following format.
$n$ $P_1$ $P_2$ $\cdots$ $P_n$
- All input values are integers.
- $1\leq T\leq 2\times 10 ^ 5$
- $1\leq n\leq 2\times 10 ^ 5$
- $1\leq P_i \leq n$
- $P$ is a permutation of $(1,2,\ldots,n)$.
- The sum of $n$ over the $T$ test cases is at most $2\times 10 ^ 5$.
Output
Output the answer for each test case in the following format.
Output the minimum inversion number $x$ of $A$ after all operations have been performed, and the lexicographically smallest $A$ among those that achieve the minimum inversion number, in the following format, followed by a newline.
$x$ $A_1$ $A_2$ $\cdots$ $A_n$
Sample
Sample 1
Input
2 4 1 4 3 2 5 5 4 3 2 1
Output
2 2 1 4 3 0 1 2 3 4 5
-
About the 1st test case
This input represents $n=4,\ P=(1,4,3,2)$.
For example, operating as follows makes the final $A$ equal to $(2,1,4,3)$.
- Add $P_1=1$ to the front of $A=()$ (the empty sequence), resulting in $A=(1)$.
- Add $P_2=4$ to the back of $A=(1)$, resulting in $A=(1,4)$.
- Add $P_3=3$ to the back of $A=(1,4)$, resulting in $A=(1,4,3)$.
- Add $P_4=2$ to the front of $A=(1,4,3)$, resulting in $A=(2,1,4,3)$.
-
About the 2nd test case
This input represents $n=5,\ P=(5,4,3,2,1)$. Choosing to add to the front for all of $i=1,2,3,4,5$ results in $A=(1,2,3,4,5)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
cureskol