序列逆序对的计算方式

题目-求逆序对

归并排序(分治)求逆序对

在归并排序向上合并的过程中, 对于两段有序的序列合并为一个序列, 如果是顺序的左边的所有数字都应该$\le$右边

因此当出现$w[p1]>w[p2]$, $[p1,mid]$和$p2$构成了逆序对, 答案需要累加
$$mid-p1+1$$

重要误区

为什么当出现$w[p1]>w[p2]$, 不能用右半边统计, 也就是$j-(mid+1)+1$

关键在于统计重复, 具体的来说, 如果前面出现了$w[i]>w[p2]$, 按照上面的方式逆序对的数量将会累计$p2-(mid+1)+1$, 但是当出现了当前情况$w[i]>w[j]$的时候$p2-(mid+1)+1$这一段将会被统计两次!, 因此是错误的

为什么统计左侧就是正确的?
当出现$w[p1]>w[p2]$的时刻, 立刻统计出$mid-p1+1$这一段都是与$w[p2]$构成逆序对, 并且统计完之后直接将$w[p2]$加入到答案序列中, 不存在重复统计的情况!

算法步骤

• 对序列进行递归划分
• 向上合并的过程中统计逆序对的数量

算法时间复杂度$O(n\log n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

LL ans;
int n, w[N], tmp[N];

void merge_sort(int l, int r) {
   
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
   
        if (w[i] <= w[j]) tmp[k++] = w[i++];
        else {
   
            ans += mid - i + 1;
            tmp[k++] = w[j++];
        }
    }

    while (i <= mid) tmp[k++] = w[i++];
    while (j <= r) tmp[k++] = w[j++];

    for (int i = 0; i < k; ++i) w[i + l] = tmp[i];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    merge_sort(0, n - 1);

    cout << ans << '\n';

    return 0;
}

树状数组求逆序对

如果一段序列是有序的, 那么对于$i<j$, 有$w_i\le w_j$, 因此对于当前位置$i$, 可以统计前面有多少个数字$>w_i$与$w_i$构成逆序对, 然后再将$w_i$加入集合中, 统计前缀和可以使用树状数组实现

算法步骤

• 因为数据范围很大, 需要对原数据进行离散化
• 实现树状数组查询和修改
• 查询对于当前位置$i$, $1\sim i-1$有多少个数字比当前数字大
• 将当前数字加入到集合当中

注意: 树状数组的下标从$1$开始, 离散化的时候需要$+1$

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, w[N];
vector<int> nums;
int tr[N];

int lowbit(int x) {
   
    return x & -x;
}

void modify(int u, int val) {
   
    for (int i = u; i <= n; i += lowbit(i)) tr[i] += val;
}

LL get(int u) {
   
    LL ans = 0;
    for (int i = u; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}


// 因为树状数组下标是从1开始, 因此需要 + 1, 否则会TLE
int find(int x) {
   
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
   
        cin >> w[i];
        nums.push_back(w[i]);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    LL ans = 0;
    for (int i = 0; i < n; ++i) {
   
        int x = find(w[i]);
        ans += get(n) - get(x);
        modify(x, 1);
    }

    cout << ans << '\n';

    return 0;
}

离散化作为树状数组边界的代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e5 + 10;

int n, w[N], m;
vector<int> nums;
int tr[N];

int lowbit(int x) {
   
    return x & -x;
}

void modify(int u, int val) {
   
    for (int i = u; i <= m; i += lowbit(i)) tr[i] += val;
}

LL get(int u) {
   
    LL ans = 0;
    for (int i = u; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

// 因为树状数组下标是从1开始, 因此需要 + 1, 否则会TLE
int find(int x) {
   
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
   
        cin >> w[i];
        nums.push_back(w[i]);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    m = nums.size();

    LL ans = 0;
    for (int i = 0; i < n; ++i) {
   
        int x = find(w[i]);
        // 注意在这里是get(m)
        ans += get(m) - get(x);
        modify(x, 1);
    }

    cout << ans << '\n';

    return 0;
}