Minimize Inversions Number
题意翻译
给定一个 $1\sim n$ 的排列 $p$。
你可以进行下列操作正好一次:
- 选定 $p$ 的一个长度为 $k$ 的子序列,并将其按照相同的顺序移动到 $p$ 的最前面。
对于 $k=0,1,\cdots,n$,分别求出 $p$ 在操作后的最小逆序对数。
每个测试点包含 $T$ 组数据。
保证:
$1\leq T\leq5\times10^4;$
$1\leq n,\sum n\leq5\times10^5;$
$p$ 是一个 $1\sim n$ 的排列。
题目描述
You are given a permutation $ p $ of length $ n $ .
You can choose any subsequence, remove it from the permutation, and insert it at the beginning of the permutation keeping the same order.
For every $ k $ from $ 0 $ to $ n $ , find the minimal possible number of inversions in the permutation after you choose a subsequence of length exactly $ k $ .
输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 50\,000 $ ) — the number of test cases.
The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 5 \cdot 10^5 $ ) — the length of the permutation.
The second line of each test case contains the permutation $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ).
It is guaranteed that the total sum of $ n $ doesn't exceed $ 5 \cdot 10^5 $ .
输出格式
For each test case output $ n + 1 $ integers. The $ i $ -th of them must be the answer for the subsequence length of $ i - 1 $ .
输入输出样例
输入样例 #1
3
1
1
4
4 2 1 3
5
5 1 3 2 4
输出样例 #1
0 0
4 2 2 1 4
5 4 2 2 1 5
说明
In the second test case:
- For the length $ 0 $ : $ [4, 2, 1, 3] \rightarrow [4, 2, 1, 3] $ : $ 4 $ inversions.
- For the length $ 1 $ : $ [4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3] $ : $ 2 $ inversions.
- For the length $ 2 $ : $ [4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3] $ , or $ [4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2] $ : $ 2 $ inversions.
- For the length $ 3 $ : $ [4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4] $ : $ 1 $ inversion.
- For the length $ 4 $ : $ [\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3] $ : $ 4 $ inversions.