Minimize Inversions Number
首先考虑\(k = 1\)，记\(g_i = \sum_{j = 1}^{i - 1} [p_i < p_j] - \sum_{j = 1}^{i - 1} [p_i > p_j]\)，那么\(g_i\)表示将\(i\)移向最前面逆序对减少的量，那么我们的就相当于求\(\max g_i\)。
在考虑\(k > 1\)，我们选择一个子序列\(a_1, a_2, ... ,a_k\)，如果我们每次把最左的数移到序列最前，那么我们的贡献就为\(\sum g_{a_i}\)，但这样移到最前面的子序列就反转了，所以我们应该，再将其反转回来，记\(inv\)为子序列的逆序对个数，那么贡献应加上\(2 * inv - \dbinom{k}{2}\)，但我们很难去动态维护\(inv\)，应该考虑子序列的特殊性质。
一个结论对于\(i < j, p_i > p_j\)，\(j\)选在子序列中一定不劣。
证明：考虑一个离\(i\)最近的\(j\)，那么一定不存在\(i < k < j\)使得\(p_k < p_j < p_i\)，那么把\(j\)移到最前面贡献一定不劣于\(i\)。
那么我们的\(inv\)就很好求了，设\(val_i\)表示将\(i\)选进子序列的贡献，那么\(val_i = g_i - 2 \sum_{j = i + 1}^n[p_i > p_j]\)。
把\(val_i\)排序，一个一个加入答案即可。
用树状数组维护,时间复杂度为\(O(n \log n)\)。
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#define IN inline
#define LL long long
using namespace std;
const int N = 5e5 + 5;
int n, a[N], T; LL f[N], g[N];
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
int lowbit(int x){return x & -x;}
void add(int x, int v){for (; x <= n; x += lowbit(x)) f[x] += v;}
LL query(int x) {
LL res = 0;
for (; x; x -= lowbit(x)) res += f[x];
return res;
}
int main() {
T = read();
for (; T; T--) {
n = read(); LL ans = 0;
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= n; i++)
ans += i - 1 - query(a[i]), g[i] = (LL)(i - 1) - 2LL * query(a[i]), add(a[i], 1);
for (int i = 1; i <= n; i++) add(a[i], -1);
for (int i = n; i >= 1; i--) g[i] -= 2LL * query(a[i]), add(a[i], 1);
for (int i = 1; i <= n; i++) add(a[i], -1);
sort(g + 1, g + 1 + n);
for (int i = 0; i <= n; i++)
printf("%lld ", ans - (LL)i * (i - 1) / 2), ans -= g[n - i]; puts("");
}
}