[CF1375E] Inversion SwapSort

[CF1375E] Inversion SwapSort - 构造

Description

给定一个长度为 (n) 的序列 (a)，求 (a) 中的所有逆序对 ((i_1, j_1), (i_2, j_2), cdots, (i_m, j_m)) 的一个排列 (p)，使得依次交换 ((a_{i_{p_1}}, a_{j_{p_1}}), (a_{i_{p_2}}, a_{j_{p_2}}), cdots, (a_{i_{p_m}}, a_{j_{p_m}})) 后序列单调不降。(1 le n le 10^3)，(1 le a_i le 10^9)

Solution

什么样的过程才能让所有逆序对（绑定位置！）恰好交换一次呢？

先问：什么样的过程才能让所有逆序对（绑定元素本身！）恰好交换一次呢？

冒泡排序

我们对序列做冒泡排序，每次记录被交换元素的下标即可

回到原问题

我们求出一个排列，表示最终每个位置要放现在哪个位置的元素

然后按上面的做法对这个排列做即可

为了方便理解这个过程，可以画一个二部图，左 b[i] 和右 i 连接

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 2);

    for (int i = 1; i <= n; i++)
        cin >> a[i].first, a[i].second = i;

    sort(&a[1], &a[n + 1]);

    vector<int> b(n + 2);
    for (int i = 1; i <= n; i++)
        b[i] = a[i].second;

    vector<pair<int, int>> ans;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j < n; j++)
            if (b[j] > b[j + 1])
            {
                ans.push_back({b[j + 1], b[j]});
                swap(b[j], b[j + 1]);
            }

    cout << ans.size() << endl;
    for (auto [x, y] : ans)
        cout << x << " " << y << endl;
}