题目大意：
给你一串数（500,000），问你给他们按大小排序至少需要调换几次（只能相邻的调换）。

思路：
下面引入概念：对于一组数n,有n*（n-1）/2对组合，现在，定义如果a[i]>a[j]&&i<j，那么数a[i]和a[j]的位置相反。现在设这一组数中，有s对数的位置相反了。那么s=b[1]+b[2]+...+b[n](b[i]表示a[i]前面有b[i]个数和他的位置相反了)。
现在证明：要想使数组a[]变成从小到大排列，那么至少需要调换s次相邻的数，并且只需要调换s次，就能成功。
1.对于a[i]>a[i+1],那么我只要调换a[i]和a[i+1],b[]数组值改变的只有b[i+1]--;即s--;也就是说，s的值只有进行一次合适的调换之后，才能减少一个，不可能通过一次调换减少2个及以上。由此得知，至少要调换s次相邻的数，s的值才能变成0，此时才可能是从小到大的顺序。另外也可以换一种想法理解这个事，现在我假设存在一串从小到大的数列，那么我显然可以通过调换若干次相邻两个数的位置，使其变成任意顺序的数列，那么，在这个过程中，每次调换a[i]和a[i+1]只会使得b[i+1]++,即s++;（当然这还是最理想的状况，有可能调换之后s--也说不定。） 我现在寻求的是，通过最少的调换次数使得s最快的增加的方法，那么，也只可能是一次调换，s增加1。这也就是说，我不可能通过少于s次的相邻数调换，使得一个从小到大的数列，变成逆序对数的和为s的数列。那我至少也要把这s次调换倒着做一遍，才可以把任意序列的数组变成标准顺序。
2.假设任意相邻的两个数调换都不能使s变小，那么一定是对于任意的i，都有a[i]>=a[i+1]。这也就是说，a[]数组已经排序完成。所以，得证，不可能出现数组还没有排序好却所有的相邻的数交换都不能使s减少的情况这也就说明了，s次调换每一次都可以使得s--，即s次调换一定可以恢复标准顺序。
综上，问题就变成了求一串数的逆序和（记从小到大为标准序）

关于时间复杂度的分析：
要是求出每个数a[i]的b[i],那么，那么，那么，一般的思路就是对于每个数，查找他前面的数有多少个比他小的。然后记录在b[]数组中，但是这样保守估计500,000*(500,000-1)/2肯定是超时了。一般数据规模500,000的话，应该就是O(n)的复杂度了，况且这道题还是多组数据输入。O(nlogn)也可以接受。

关于树状数组：
这个树状数组求逆序对数看了好半天才看明白。

首先先说一下什么是树状数组吧，我理解的应该就是线段树的变形（也可能线段树是树状数组的变形，只不过我先知道的线段数）。其实大概就是把数合组，首先两个合成一组。然后再四个合成一大组，八个合成更大一组，以此类推。然后合成的组可以代替该组的最大标号数据。如图：



然后就是用树状数组求逆序对数了，首先先是建好空的如上图的树状数组（c数组的值都为0，但是树状数组的大小已经知道了）。然后一个一个的按照顺序添加数（加入j就是把a[j]赋值成1），在这个过程中，每一个瞬间c[i]都表示当前时刻i组（以第i号数为尾的最大组）有多少个数在数组里了。每添加一个a[i]，都会改变若干个c[]数组的值，同时可以确定s[i](该数组在数i前面有多少个比i还小的数)，确定方法，比如：s[6]=c[6]+c[4];s[8]=c[7]+c[6]+c[4];此时也就确定了该数组在第j个数i之前有多少个比它大的数j-s[i]。

总结：这么存这个数的好处就是，有规律的把一串数分成几个合适大小的组，这样既不会使得层数太高（比如c[i]表示前i个数怎么怎么样就是太高了），也可以很方便的访问几个连续的数的总结果。

 

另外关于离散化（我觉得就是把一堆数密集化啊@_@）的问题，我觉得还是用结构体比较方便啊~

 

关于为什么要是归并排序而不是冒泡排序：

冒泡排序超时啊，这不是废话吗，但是，假如不超时，那么，冒泡排序过程中调换的次数是不是就是最少的相邻调换次数。每次调换都可以使s--，显然得出的次数就是逆序对数。那为什么冒泡排序比归并排序慢呢，简单一想，肯定是因为做了太多的并不需要交换位置的判断。


#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #define N 500000+500 using namespace std; int n; int b[N]={0};//离散化之后的数 bool a[N]={0};//标记数i是否已经在数组里面了 int c[N]={0};//树状数组的那个值呗~ int s[N]={0};//数i前面有s[i]个数比它大 //int m[N]={0};//数i前面有m[i]个数比它小 struct shu { int v; int ord; }d[N]={0}; bool cmp1(shu a,shu b) { if(a.v<b.v)return 1; else return 0; } void init()//预处理，输入并离散化处理 { for(int i=1;i<=n;i++)//输入n个数（1-n） { scanf("%d",&d[i].v); d[i].ord=i; } sort(d+1,d+n+1,cmp1); for(int i=1;i<=n;i++) { b[d[i].ord]=i; } } void ceshi1() { for(int i=1;i<=n;i++) { cout<<b[i]<<" "; } cout<<endl; } void add(int x)//把x加入到数状数组中 { a[x]=1; int t=x; while(t<=n) { c[t]++; t+=(t&(-t)); } } int out(int x)//把数x之前(包括x)的所有a都加在一起（即合适的c加到一起） { int s=0; while(x>0) { s+=c[x]; x=x-(x&(-x)); } return s; } void sol() { for(int i=1;i<=n;i++) { add(b[i]);//把b数组第i个数加入到数组中 s[i]=i-out(b[i]); } } int main() { while(cin>>n) { if(n==0)break; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); init(); //ceshi1(); long long int sum=0; sol(); for(int i=1;i<=n;i++) { sum+=s[i]; } printf("%lld\n",sum); } }


注：最后关于树状数组访问时和插入一个数据后，如何寻找需要的节点的问题，会找时间证明。


注意这里还有一个比较重要的问题我还没有太想明白，就是，在进行数组离散化处理的时候，如果有两个值相同的元素，把他离散化处理成两个大小不同的数，会不会对结果有影响。以前没主要到这个问题，但是ac了，找时间要好好考虑一下。3.29