$cover$

求逆序对的三种方法

DBZQ

14789人浏览 · 2021-12-13 18:32:51

DBZQ · 2021-12-13 18:32:51 发布

逆序对的定义：对序列 $a_1,a_2,a_3......a_n$ ，存在 $i<j$ 且 $a_i>a_j$ ，那么这是一个逆序对

第一种：暴力求解

第二种：归并排序

第三种：树状数组

第一种：暴力求解

$N^2$ 暴力，这里我就不写了。

第二种：归并排序

归并排序的原理就是将一个序列无限二分，直到每个部分只有一个元素，那这部分就是有序的了，再对两个元素就行比较排序，分别放入左半部分和右半部分；对左半部分和右半部分分别进行有序插入后合并，如此反复......

例如，我们现在有两个部分：

1 3 5 7 9

2 4 6 8 10

现在进行合并，对两个部分的第一个数进行比较。

因为 1 < 2，所以将 1 放入临时数组（也就是答案数组），这时临时数组只有一个元素

然后因为 3 > 2，所以将 2 放入临时数组，这时临时数组有两个元素

1 2

然后因为 3 < 4，所以将 3 放入临时数组，这是临时数组有三个元素

1 2 3

......

如此反复，最后得到的临时数组有十个元素

1 2 3 4 5 6 7 8 9 10

那么我们再来看一下逆序对是怎么求的，在第三步之后，我们需要比较 4 和 5 的大小，因为 4 小于 5 ，又因为左半部分数组是有序（递增）的，所以左半部分剩下的所有元素均大于 4 ，也就是说左半部分剩下的所有数均可以和 4 构成逆序对，左半部分剩下元素 5 7 9 三个元素，所以对 4 而言，有三个逆序对（5，4）（7，4）（9，4），其余同理......

实现代码：

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

#define int long long

int n, ans = 0;
int a[100010], temp[100010];
void merge_pai(int l, int r, int mid) {
	int i = l, p = l, j = mid;
	while (i < mid && j <= r) {
		if (a[i] <= a[j])	 	temp[p++] = a[i++];
		else {
			temp[p++] = a[j++];
			ans += mid - i;//核心，逆序对在这里
		}
	}
	while (i < mid)		temp[p++] = a[i++];//防止a[]中前面的数还没有移完
	while (j <= r)		temp[p++] = a[j++];//防止a[]中后面的数还没有移完
	p = i = l;
	while (p <= r)		a[i++] = temp[p++];//转移到a[]中
}
void merge_sort(int l, int r) {
	if (l < r) {
		int mid = (l + r) / 2;
		merge_sort(l, mid);
		merge_sort(mid + 1, r);
		merge_pai(l, r, mid + 1);
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)		cin >> a[i];
	merge_sort(1, n);
	cout << ans << endl;
}

第三种：树状数组

树状数组的原理我就不阐述了。

树状数组是用来区间求和的，可以快速求出一段区间内的数的和。

那么我们应该怎样利用这个性质呢？

对于一个数，如果比它大的数在它之前出现，那么这是一对逆序对。

那么我们在对某个数进行统计时，我们需要统计一下比它大并且在它之前出现的数，这个时候我们就可以使用 tree 数组进行标记，如果一个数出现过了，我们将相应的 tree 数组标记为 1 ，（例如第一个数为 1 ，那么我们将 tree[1] 标记为 1 ，第二个数为 4 ，那么我们将 tree[4] 标记为1 ......）。

例如，我们对数组进行O(n)遍历，将遍历到的数标记为 1 ，表示出现过

原数组	1 4 3 5 6 2
遍历第一次后的 tree 数组	1 0 0 0 0 0
遍历第二次后的 tree 数组	1 0 0 1 0 0
遍历第三次后的 tree 数组	1 0 1 1 0 0
遍历第四次后的 tree 数组	1 0 1 1 1 0
遍历第五次后的 tree 数组	1 0 1 1 1 1
遍历第六次后的 tree 数组	1 1 1 1 1 1

我们在遍历第三次时，此时 $a_3$ = 3，标记 tree[3] = 1，对区间 [1, 3] 求和，sum[1~3] = tree[1] + tree[2] + tree[3] = 2，然而我们在进行第三次遍历，所以此时应该有三个数，但求和发现范围 1~3目前只有两个数出现过（因为sum[1~3] = 2），说明还有一个数我们没有找到，我们是对区间 [1, 3] 求和，所以还有一个数应该比 3 大并且在 3 之前出现，所以这是一个逆序对，其他同理......

对于第 $m$ 次遍历（ $a_m$ ）时，如果 $sum[1,a_m]=k$ ，那么 $a_m$ 作为第二个数时的逆序对有 $m-k$ 对

实现代码：

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

#define int long long

const int N = 5e6 + 10;
int tr[N * 2], n;

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

void add(int x, int v) {
    while (x <= n) {//这里的n是最大值，必要时需要进行离散化
        tr[x] += v;
        x += lowbit(x);
    }
}

int sum(int x) {
    int ans = 0;
    while (x) {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

signed main() {
    int ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v; cin >> v;
        add(v, 1);
        ans += i - sum(v);
    }
    cout << ans << endl;
}