题目链接：?id=2299题目大意：求逆序数题目分析：以前学的用树状数组求逆序数，补一下归并排序的求法，，感觉实现起来更简单，归并排序自顶向下分解，自底向上合并，每次合并的两个区间都是已经排好序了的，这就给我们求逆序数带来了很大的好处我们把一个大区间[l,r]分成[l,mid], [mid + 1, r]，显然每次我们只要求一个数在左区间，一个数在右区间时的逆序数个数，而不用考虑左区间内和右区间内的逆序数个数，因为合并是自底向上的，左区间和右区间内的逆序数我们已经在他们的子状态中求结果了，所以在自底向上合并时，我们直接累加每一层的逆序数个数就是最后整个区间的逆序数了。很赞的应用，对递归有了更深刻的理解#include <cstdio>#include <cstring>#include <algorithm>#define ll long longusing namespace std;int const MAX = 500005;int a[MAX], n;ll ans;void Merge(int l, int mid, int r){int i = l, j = mid + 1;while(i <= mid && j <= r){if(a[i] <= a[j])i ++;else{j ++;//因为左右区间都是有序的，因此a[i]>a[j]说明a[i]~a[mid]都大于a[j]ans += mid – i + 1;}}sort(a + l, a + r + 1);return;}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(l, mid, r);}return;}int main(){while(scanf("%d", &n) != EOF && n){ans = 0;for(int i = 0; i < n; i++)scanf("%d", &a[i]);Merge_sort(0, n – 1);printf("%lld\n", ans);}}
就是去做你害怕的事，直到你获得成功的经验。
