POJ 2299 Ultra-QuickSort【树状数组，逆序数】

题意：给出一组数，然后求它的逆序数

先把这组数离散化，大概就是编上号的意思---

然后利用树状数组求出每个数前面有多少个数比它小，再通过这个数的位置，就可以求出前面有多少个数比它大了

这一篇讲得很详细

http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=500005;
17 
18 int n;
19 int a[maxn];
20 int bit[maxn];//树状数组 
21 
22 struct node{
23     int x,id;
24 } p[maxn];
25 
26 int cmp(node n1,node n2){
27     return n1.x < n2.x;
28 }
29 
30 int lowbit(int x){ return x & (-x);}
31 
32 void add(int i, int x){
33     while(i <= n){
34         bit[i]+=x;
35         i += lowbit(i);
36     }
37 }
38 
39 int sum (int i){
40     int s=0;
41     while ( i > 0){
42         s += bit[i];
43         i -= lowbit(i);
44     }
45     return s;
46 } 
47 
48 int main(){
49     while(scanf("%d",&n),n){
50         for(int i=1;i<=n;i++){
51             scanf("%d",&p[i].x);
52             p[i].id=i;
53         }
54         sort(p+1,p+n+1,cmp);
55         for(int i=1;i<=n;i++) a[p[i].id] = i;
56         
57         memset(bit, 0, sizeof(bit));
58         LL ans=0;
59         for(int i=1; i <= n; i++) {
60            add(a[i],1);
61            ans += i - sum(a[i]); 
62         }
63         printf("%I64d
",ans);
64     }
65     return 0;
66 }

View Code

树状数组的第一道题目---------------加油-------

gooooooooooooo--------------------------------------

POJ 2299 Ultra-QuickSort【树状数组 ，逆序数】

POJ 2299 Ultra-QuickSort【树状数组，逆序数】