No.1867 Partitions and Inversions
タグ : / 解いたユーザー数 15
作問者 :
Forested
ぷら
shiomusubi496
Problem Statement
You are given an integer $N$ and a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$. For each $k = 1, 2, \cdots , N$, solve the following problem.
You perform the following operation on $P$ exactly $1$ time.
First, create an integer sequence $A = (A_1, A_2, \ldots, A_{k+1})$ of length $k+1$ satisfying the following condition.
$1 = A_1 < A_2 < \cdots < A_{k+1} = N+1$
Then, for each $i = 1, 2, \ldots, k$, sort $P_{A_i}\ , P_{A_i + 1}\ , \ldots, P_{A_{i+1} - 1}$ in ascending order.
Find the minimum possible value of the inversion number of $P$ after the operation.
Note that the problems are independent, and an operation does not affect the other problems.
Definition of the inversion number (click to expand)
For a sequence $P$ of length $N$, the inversion number is defined as the number of integer pairs $(a, b)$ satisfying all of the following.
- $1 \leq a < b \leq N$
- $P_a > P_b$
Input
$N$ $P_1$ $P_2$ $\cdots$ $P_N$
- All inputs are integers.
- $1 \leq N \leq 3000$
- $P$ is a permutation of $(1, 2, \ldots, N)$.
Output
Print $N$ lines. On the $i$-th line, print the answer for the case $k = i$.
Sample
Sample 1
Input
5 2 4 3 5 1
Output
0 1 3 4 5
Consider the case $k=3$ as an example.
If $A = (1, 2, 3, 6)$, then $P$ finally becomes $(2, 4, 1, 3, 5)$. The inversion number of this $P$ is $3$. This choice is $1$ of the optimal ones.
Sample 2
Input
6 1 2 3 4 5 6
Output
0 0 0 0 0 0
The inversion number of $P$ is $0$ from the beginning, so the answer is $0$ for any $k$.
Sample 3
Input
15 7 13 6 2 12 11 10 4 8 15 9 14 5 3 1
Output
0 6 17 22 23 31 38 44 46 49 54 57 60 62 63
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。