QOJ 8052 题解。

联考 T1 考到了这个题，全机房都过了，就我不会呜呜呜。

Task

给长度为 $n$ 的排列 $a$。一次操作可以交换 $a$ 相邻的两个数，问最少多少次操作后 $a$ 满足 $\forall 1 \le i < j \le n, a_i i \le a_j j$。

$n \le 5 \times 10^5$。

Solution

记 $pos_{a_i} = i$。

考虑如果最终的排列 $a$ 如果满足 $a_i = i$，则一定合法，操作次数为逆序对数。

然而不止有这一种最终排列方式。如果交换两个相邻的数，变成：$1, 2, \cdots, x, x + 2, x + 1, x + 3, \cdots, n$，同样是合法的。

可以发现，最终排列一定可以 $a_i = i$ 的排列通过交换若干个不相交的相邻数得到。

考虑一个 $pos_i > pos_{i + 1}$，说明 $i$ 原本在 $i + 1$ 后面，最后只需交换成 $i + 1, i$ 即可，无需再花费一次操作交换为 $i, i + 1$。

用逆序对数减去 $\sum_{i = 1}^{n - 1}[pos_i > pos_{i + 1}]$ 即可。

复杂度 $O(n \log n)$。

Code

#include <bits/stdc++.h>
#define _for(i, a, b)  for (int i = (a); i <= (b); i ++ )
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n, pos[N]; ll ans;
struct BIT {
    int tr[N];
    inline int lowbit(int x) { return (x & ( - x)); }
    inline void update(int x, int k) { for (int i = x; i <= n; i += lowbit(i))  tr[i] += k; }
    inline int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))  res += tr[i];
        return res;
    }
    inline int query(int l, int r) { return query(r) - query(l - 1); }
} T;
inline void solve() {
    cin >> n, ans = 0; int x;
    _for (i, 1, n)  cin >> x, pos[x] = i, ans += T.query(x + 1, n), T.update(x, 1);
    _for (i, 1, n - 1)  if (pos[i] > pos[i + 1])  ans -- , i ++ ;
    cout << ans << "\n";
    _for (i, 1, n)  T.update(i, - 1);
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T -- )  solve();
    return 0;
}