逆序对的定义：对序列 ，存在 且 ，那么这是一个逆序对
目录
第一种：暴力求解
第二种：归并排序
第三种：树状数组
第一种：暴力求解
暴力，这里我就不写了。
第二种：归并排序
归并排序的原理就是将一个序列无限二分，直到每个部分只有一个元素，那这部分就是有序的了，再对两个元素就行比较排序，分别放入左半部分和右半部分；对左半部分和右半部分分别进行有序插入后合并，如此反复......
例如，我们现在有两个部分：
1 3 5 7 92 4 6 8 10
现在进行合并，对两个部分的第一个数进行比较。
因为 1 < 2，所以将 1 放入临时数组（也就是答案数组），这时临时数组只有一个元素
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
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
我们在遍历第三次时，此时 = 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 之前出现，所以这是一个逆序对，其他同理......
对于第 次遍历（）时，如果 ，那么 作为第二个数时的逆序对有 对
实现代码：
#define _CRT_SECURE_NO_WARNINGS
#include
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;
}