思路
- 最优解中,总交换次数等于序列的逆序对个数。原因是交换相邻位置最多减少 $1$ 个逆序对(不影响它们和前后元素的相对位置),而升序序列的逆序对个数为零,因此至少需要交换 $k$ 次。又因为冒泡排序每次交换都可以减少 $1$ 个逆序对,所以只需要交换 $k$ 次。
- 最优解中,每个元素的交换次数固定。记 $l_i$ 为 $a_i$ 左边比它大的数的个数,$r_i$ 为 $a_i$ 右边比它小的数的个数,则 $a_i$ 的交换次数为 $l_i + r_i$。证明:首先,每个左边比 $a_i$ 大的数必然要和它交换才能到它后面,右边比它小的数也必须和它交换才能到它前面,因此至少需要 $l_i + r_i$ 次交换。其次,$\sum_{i = 1}^{n} (l_i + r_i) = 2k$,其中 $k$ 是整个序列的逆序对个数。假设最优解中 $a_i$ 需要交换 $x_i$ 次,有 $x_i \ge l_i + r_i$,因此 $\sum_{i = 1}^{n} x_i \ge 2k$。又由于整个序列只需交换 $k$ 次,因此 $\sum_{i = 1}^{n} x_i = 2k$(每交换一次会使两个元素的交换次数分别加一),因此 $x_i = l_i + r_i$(反证,假设存在 $x_i > l_i + r_i$,则 $\sum_{i = 1}^{n} x_i > 2k$,则总交换次数(等于每个元素的交换次数之和除以 $2$)大于 $k$,这与它是最优解矛盾)。
因此我们需要知道每个数左边有多少个数比它大,右边有多少个数比它小,可用树状数组维护 $1 \sim x$ 中有多少个数,起初为零,遍历到 $a_i$,就使 $a_i$ 的位置加一。
(() => {
let buf = [], i = 0;
const rl = require('readline').createInterface({ input: process.stdin });
rl.on('line', ln => buf.push(ln));
rl.once('close', () => main(dt => buf[i++].split(' ').map(dt), console.log));
})();
const N = 100010;
let n, m, a, b, k = Array(N).fill(0), tr = Array(N).fill(0);
const lowbit = x => x & -x;
function id(x) {
let l = 0, r = m - 1;
while (l < r) {
const mid = l + r >> 1;
if (b[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
function sum(x) {
let s = 0;
for (let i = x; i; i -= lowbit(i)) s += tr[i];
return s;
}
function add(x, c) {
for (let i = x; i <= m; i += lowbit(i)) tr[i] += c;
}
function main(input, print) {
[n] = input(Number);
a = input(Number);
// 若 a[i] 过大可离散化
b = [...new Set(a)];
b.sort((a, b) => a - b);
m = b.length;
a = a.map(x => id(x));
for (let i = 1; i <= n; i++) {
const h = a[i - 1];
k[i] = sum(m) - sum(h);
add(h, 1);
}
let ans = 0;
tr = Array(N).fill(0);
for (let i = n; i; i--) {
const h = a[i - 1];
k[i] += sum(h - 1);
ans += (1 + k[i]) * k[i] / 2;
add(h, 1);
}
print(ans);
}