http://acm.hust.edu.cn/vjudge/contest/124435#problem/D
题意：给出一个长度为n的数列，你每一次可以随意交换其中两个数字的位置。问你至少交换几次，才能使得这个数列是个单调递增数列。
比赛时没做出来，（自然，比赛后也没做出来。。。）
找了度娘后，发现有三种方法（线段树， 树状数组， 归并排序），然而我一种也不会。
**************************************************************************************************************************************
下面介绍介绍归并排序：
由于本题实际上就是要求逆序对（即满足i<j，a[i]>a[j]的数对）的个数。而我们再回顾一下归并排序的过程：
假设回溯到某一步，后面的两部分已经排好序（就是说当前需要归并的两个部分都是分别有序的），假设这两个序列为
序列a1：2 3 5 9
序列a2：1 4 6 8
此时我们的目的就是要将a1和a2合并为一个序列。
由于在没排序前a2序列一定全部都是在a1序列之后的，当我们比较a2的1与a1的2时，发现1<2按照归并的思想就会先记录下a2的1，而这里实际上就是对冒泡排序的优化，冒泡是将a2的1依次与a1的9,5,3,2交换就需要4次，而归并却只有一次就完成了，要怎么去记录这个4呢，实际上由于1比2小而2后面还有4个数，也就是说那我的结果就必须要+4，也就是记录a1序列找到第一个比a2某一个大的数，他后面还余下的数的个数就是要交换的次数。
同时我们看a2的4时，a1中第一个比它大的数是5,5之后共有两个数，那结果就+2,。依次下去就可以计算出结果。但是由于我们任然没有改变归并排序的过程。所以复杂度还是O(nlogn)。
#include <stdio.h> #include <string.h> #define maxn 500010 int n, A[maxn], T[maxn]; long long ans;void Merg_Sort(int x, int y) {if(y-x<=1) return ;int mid=x+(y-x)/2;Merg_Sort(x, mid);Merg_Sort(mid, y);int p=x, q=mid, i=x;while(p<mid || q<y){if(q>=y || (p<mid && A[p]<=A[q])) T[i++]=A[p++];else//else的条件是(p==mid || A[q] < A[p]) {if(p<mid) ans+=(mid-p);//由于是p<mid,所以此时也就是相当于 A[q] < A[p]T[i++] = A[q++]; //上面同时A[p]是第一个<A[q]的数，所以+后面还有的数(mid-p) }}for(i=x; i<y; i++)A[i] = T[i]; }int main() {while(scanf("%d", &n),n){memset(A, 0, sizeof(A));memset(T, 0, sizeof(T));for(int i=0; i<n; i++)scanf("%d", &A[i]);ans = 0;Merg_Sort(0, n);printf("%I64d\n", ans);}return 0; }
