Solve

POJ2299树状数组

题目解答

求逆序对，这类问题解法很多，首先想想为何不直接快排然后统计交换次数。

这里介绍一种树状数组的解法：因为数字本身很大，我们要进行一次离散化。离散化就是每个只要保存他们的相对位置即可，这样能极大压缩树状数组的空间从而避免MLE。
例如：2 4 1 10 可以被离散化为 2 3 1 4。

先对一个镜像数列排序，之后从有序的数列中二分查找每个数组的位置，用位置替换原本的值即可，离散化时间复杂度：O(NlogN)。
之后顺理成章的用树状数组统计即可。

运行情况

POJ2299

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio> 
#include<iostream>
#include<cstdlib>
#define MAX(a,b) ((a)>(b)?1:-1)
#define BIG 500003
using namespace std;

typedef long long int64;
int64 n,tot,pai[BIG],num[BIG],sum[BIG],ln,rn,mid;
inline int64 lowbit(int64 x){return (x & ((x-1)^x));}
inline void  change(int64 k,int64 delta){
       while(k<=n){
         sum[k]+=delta;
         k+=lowbit(k);
       }
}
inline int64 getsum(int64 k){
       long total=0;
       while(k>0){
         total+=sum[k];
         k-=lowbit(k);
       }
       return total;
}
int cmp(const void *a,const void *b){
     int64 p=*(int64*)a,q=*(int64* )b;
     if(p==q) return 0;
     return MAX(p,q);
}
int main(){
    while(scanf("%I64d",&n) && n){
      for(long i=1;i<=n;i++){
        scanf("%I64d",&pai[i]);
        num[i]=pai[i];
        sum[i]=0;
      }
      tot=0; pai[0]=-BIG;
      qsort(pai,n+1,sizeof(int64),cmp);
      for(long i=1;i<=n;i++){
        ln=1;rn=n;
        while(ln<rn){
          mid=(ln+rn+1)>>1;
          if(num[i]>=pai[mid]) ln=mid;
          else rn=mid-1;
        }
        num[i]=ln;
      }
      for(long i=n;i>=1;i--){
        tot+=getsum(num[i]-1);
        change(num[i],1);
      }
      printf("%I64d\n",tot);
    }
    return 0;
}

难易等级

Middle (省选)