No.2665 Minimize Inversions of Deque
タグ : / 解いたユーザー数 108
作問者 :
suisen
/ テスター :
👑 
p-adic
cureskol
ygussany
問題文
$(1,2,\ldots,n)$ の順列 $P=(P_1,P_2,\ldots,P_n)$ が与えられます。
列 $A$ は初め空であり、あなたは $i=1,2,\ldots,n$ の順に次の操作を行います。
- $A$ の先頭または末尾に $P_i$ を追加する
全ての操作を終えた時点での $A$ の転倒数の最小値を求めてください。
また、転倒数が最小となる $A$ のうち辞書順最小のものを求めてください。
$1$ つのファイルにつき $T$ 個のテストケースが与えられるので、そのすべてに対して上記の問題を解いてください。
転倒数の定義
数列 $X=(X_1,X_2,\ldots,X_m)$ の転倒数とは、$1\leq i\lt j\leq m$ かつ $X_i\gt X_j$ を満たす整数組 $(i,j)$ の個数のことを言います。辞書順の定義
数列 $X=(X_1,X_2,\ldots,X_m),\ Y=(Y_1,Y_2,\ldots,Y_m)$ に対して、$X\neq Y$ ならば次の $2$ つを満たす $i\in\lbrace 1,2,\ldots,m\rbrace$ が唯一つ存在します。- 任意の $i$ 未満の正整数 $j$ について $X_j=Y_j$
- $X_i\neq Y_i$
このような $i$ に対して、$X_i\lt Y_i$ のとき、またそのときに限り $X$ は辞書順で $Y$ よりも小さいと言います。
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$
ここで $i=1,2,\ldots,T$ に対して $\mathrm{testcase}_i$ は $i$ 個目のテストケースを表し、次の形式で与えられます。
$n$ $P_1$ $P_2$ $\cdots$ $P_n$
- 入力は全て整数で与えられる
- $1\leq T\leq 2\times 10 ^ 5$
- $1\leq n\leq 2\times 10 ^ 5$
- $1\leq P_i \leq n$
- $P$ は $(1,2,\ldots,n)$ の順列
- $T$ 個のテストケースにわたる $n$ の総和は $2\times 10 ^ 5$ 以下
出力
各テストケースに対する答えを以下の形式で出力してください。
全ての操作を終えた時点での $A$ の転倒数の最小値 $x$ と、転倒数が最小となる $A$ のうち辞書順最小のものを次の形式で出力して改行してください。
$x$ $A_1$ $A_2$ $\cdots$ $A_n$
サンプル
サンプル1
入力
2 4 1 4 3 2 5 5 4 3 2 1
出力
2 2 1 4 3 0 1 2 3 4 5
-
1 つめのテストケースについて
この入力は $n=4,\ P=(1,4,3,2)$ を表します。
例えば以下のように操作することで最終的な $A$ は $(2,1,4,3)$ となります。
- $A=()$ (空列) の先頭に $P_1=1$ を追加して $A=(1)$ となる
- $A=(1)$ の末尾に $P_2=4$ を追加して $A=(1,4)$ となる
- $A=(1,4)$ の末尾に $P_3=3$ を追加して $A=(1,4,3)$ となる
- $A=(1,4,3)$ の先頭に $P_4=2$ を追加して $A=(2,1,4,3)$ となる
-
2 つめのテストケースについて
この入力は $n=5,\ P=(5,4,3,2,1)$ を表します。$i=1,2,3,4,5$ の全てについて、先頭への追加を選択することで $A=(1,2,3,4,5)$ となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。