一個求逆序?qū)Φ念}，N個數(shù)，N<=500000，問排成遞增序列需要相鄰的數(shù)交換多少次。一開始沒有仔細看題，上來就做，后來才發(fā)現(xiàn)數(shù)的范圍是999999999。因為最多500000個數(shù)，所以數(shù)和數(shù)之間的間隔很大，可以處理一下，使數(shù)的間隔變小，然后使用樹狀數(shù)組統(tǒng)計某個數(shù)前邊的比它大的數(shù)的個數(shù)。將所有的數(shù)放到一個結(jié)構(gòu)體里，稱作num，并增加一個成員id，然后按num遞增排列，再另開一個數(shù)組給每個數(shù)重新編號，使數(shù)的范圍都在N以內(nèi)。然后就可以很自然的用樹狀數(shù)組做了。時間500ms。據(jù)說歸并排序比這個要快。
Code：
1 #include<iostream>
2 #include<algorithm>
3 #define M 500001
4 using namespace std;
5 int c[M],aa[M],n; //aa數(shù)組為排序后重新編號用
6 struct digit
7 {
8 int num,id;
9 }a[M]; //num為數(shù)的大小
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; //最小的數(shù)編號為1
43 for(i=2;i<=n;++i){
44 if(a[a[i].id].num!=a[a[i-1].id].num) //如果前后兩個數(shù)不等，則編號為下標
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])); //每次累加該數(shù)前邊比它大的數(shù)的個數(shù)
53 }
54 printf("%lld\n",ans);
55 }
56 }