問題一覧 > 通常問題

No.2665 Minimize Inversions of Deque

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 102
作問者 : suisensuisen / テスター : 👑 p-adicp-adic cureskolcureskol 👑 ygussanyygussany
1 ProblemId : 10493 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-29 19:02:15

問題文

$(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$ が唯一つ存在します。
  1. 任意の $i$ 未満の正整数 $j$ について $X_j=Y_j$
  2. $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)$ となります。

    1. $A=()$ (空列) の先頭に $P_1=1$ を追加して $A=(1)$ となる
    2. $A=(1)$ の末尾に $P_2=4$ を追加して $A=(1,4)$ となる
    3. $A=(1,4)$ の末尾に $P_3=3$ を追加して $A=(1,4,3)$ となる
    4. $A=(1,4,3)$ の先頭に $P_4=2$ を追加して $A=(2,1,4,3)$ となる

    この $A$ の転倒数は $2$ です。転倒数を $2$ 未満にできないこと、また転倒数が $2$ で辞書順が $A$ より小さい列を得ることはできないことを証明できるので、この入力に対する答えは $(2,1,4,3)$ となります。

    特に、$A=(2,3,1,4)$ は最終的な $A$ として有り得る列であり、また転倒数は $2$ ですが、辞書順において $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。