网站制作者/推广项目网站

AcWing 788.逆序对的数量

题意

给n个数，求数列中的逆序对数量， i < j 且 a[i] > a[j] 则为一个逆序对

分析

1.可以使用穷举，把每个数和后面的数一一进行比较，每次操作的时间复杂度是O(n)，有n次操作，最终时间复杂度为O(n*n)
2.可以排序后再比较？不行！排序会把索引弄乱
3.但是可以在归并排序的过程中找出逆序对的数量。说真的，我还真没想到这题能使用分治的思想来解决。分治法在“治”的过程中，还真没有改变元素的相对顺序

代码

#include <iostream>
#define ll long longusing namespace std;const int N = 1e5 + 10;int a[N], tmp[N], n;ll s(int q[], int l, int r) {if (l >= r) return 0;int mid = l + r >> 1;ll ans = s(q, l, mid) + s(q, mid + 1, r);int i = l, j = mid + 1, t = 0;while (i <= mid && j <= r) {if (q[i] <= q[j]) tmp[t++] = q[i++];else {/*下面这代码非常关键，左半段的某个元素比右半段的某个元素大，那么左半段这个元素以及这个元素后面的所有元素都比右半段那个元素大，因此这些元素就能构成逆序对，mid-i代表后面的所有元素，再加上1是包括自己本身*/ans += mid - i + 1;tmp[t++] = q[j++];}}while (i <= mid) tmp[t++] = q[i++];while (j <= r) tmp[t++] = q[j++];int x = 0;while (l <= r) q[l++] = tmp[x++];return ans;
}int main() {cin >> n;for (int i = 0; i < n; i++) scanf("%d", &a[i]);cout << s(a, 0, n - 1);
}