poj2299 ( bit )

树状数组求逆序数，先排个序，从大到小往插，计算在他的前面有几个比他大，就是他的逆序数。

（PS：最近对数量越来越不敏感了，老在这上面错。多做题，不能断啊）

 1 #include <cstdio>
 2 #include<algorithm>
 3 #include <vector>
 4 using namespace std;
 5 typedef long long i64;
 6 struct po
 7 {
 8    int num,ord;
 9 } p[500050];
10 int a[500050];
11 template<typename T = int>
12 struct BIT {
13     vector<T> a;
14     void init(int n) {
15         vector<T>(n+1).swap(a);
16     }
17     void add(int i, T v) {
18         for(int j = i + 1; j < (int)a.size(); j = (j|(j-1)) + 1) {
19             a[j] += v;
20         }
21     }
22     T sum(int i) const {
23         T ret = T();
24         for(int j = i; j > 0; j = j & (j-1)) {
25             ret += a[j];
26         }
27         return ret;
28     }
29     T get(int i) const {
30         return sum(i+1) - sum(i);
31     }
32     void set(int i, T v) {
33         add(i, v - get(i));
34     }
35 };
36 int cmp(po a,po b)
37 {
38     if(a.num>=b.num) return 1;
39     else return 0;
40 }
41 int main( ) {
42     int n;
43     while( scanf("%d", &n) != EOF&&n )
44     {
45         BIT<int> bit;
46         bit.init(n);
47         for(int i=0;i<n;i++)
48         {
49             scanf("%d",&p[i].num);
50             p[i].ord=i;
51         }
52         sort(p,p+n,cmp);
53         i64 summ=0;
54         for(int i=0;i<n;i++)
55         {
56             bit.set(p[i].ord,1);
57             summ+=bit.sum(p[i].ord);
58         }
59         printf("%lld
",summ);
60     }
61     return 0;
62 }