一个求逆序对的题，N个数，N<=500000，问排成递增序列需要相邻的数交换多少次。一开始没有仔细看题，上来就做，后来才发现数的范围是999999999。因为最多500000个数，所以数和数之间的间隔很大，可以处理一下，使数的间隔变小，然后使用树状数组统计某个数前边的比它大的数的个数。将所有的数放到一个结构体里，称作num，并增加一个成员id，然后按num递增排列，再另开一个数组给每个数重新编号，使数的范围都在N以内。然后就可以很自然的用树状数组做了。时间500ms。据说归并排序比这个要快。
Code：
1 #include<iostream>
2 #include<algorithm>
3 #define M 500001
4 using namespace std;
5 int c[M],aa[M],n; //aa数组为排序后重新编号用
6 struct digit
7 {
8 int num,id;
9 }a[M]; //num为数的大小
10 bool cmp(digit a,digit b){
11 return a.num<b.num;
12 }
13 int lowbit(int t){
14 return t&(t^(t-1));
15 }
16 int sum(int t){
17 int total=0;
18 while(t>0){
19 total+=c[t];
20 t-=lowbit(t);
21 }
22 return total;
23 }
24 void update(int t,int key){
25 while(t<=n){
26 c[t]+=key;
27 t+=lowbit(t);
28 }
29 }
30 int main()
31 {
32 int i,j;
33 long long ans;
34 while(scanf("%d",&n),n){
35 memset(c,0,sizeof(c));
36 ans=0;
37 for(i=1;i<=n;i++){
38 scanf("%d",&a[i].num);
39 a[i].id=i;
40 }
41 sort(a+1,a+n+1,cmp);
42 aa[a[1].id]=1; //最小的数编号为1
43 for(i=2;i<=n;++i){
44 if(a[a[i].id].num!=a[a[i-1].id].num) //如果前后两个数不等，则编号为下标
45 aa[a[i].id]=i;
46 else
47 aa[a[i].id]=aa[a[i-1].id]; //否则编号与前一个相同
48 }
49 //for(i=1;i<=n;i++) printf("%d ",aa[i]);
50 for(i=1;i<=n;++i){
51 update(aa[i],1);
52 ans+=(sum(n)-sum(aa[i])); //每次累加该数前边比它大的数的个数
53 }
54 printf("%lld\n",ans);
55 }
56 }