LA 4329 pingpong 树状数组

LA 4329 pingpong

P197

树状数组统计，统计数组中，一个值的左边比它小的个数

用乘法原理求方法总数。

注意

　　N个数互不相同(distinct)

　　因为，最大值有限。可以利用树状数组统计。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 
 6 #define lowbit(x) ((x)&(-(x)))
 7 using namespace std;
 8 
 9 const int max_a=100000+1000;
10 const int max_num=20000+200;
11 
12 typedef long long LL;
13 
14 int a[20000+200];
15 LL cc[20000+200],dd[20000+200];
16 int n=max_a,C[max_a];
17 
18 int sum(int x) {
19     int ret = 0;
20     while ( x>0 ) {
21         ret += C[x];
22         x -= lowbit(x);
23     }
24     return ret;
25 }
26 
27 void add(int x, int d) {
28     while(x <= n) {
29         C[x] += d;
30         x += lowbit(x);
31     }
32 }
33 
34 int main()
35 {
36     //freopen("input.txt","r",stdin);
37     int T;cin>>T;
38     int num;
39     for(int tt=1;tt<=T;tt++) {
40         scanf("%d",&num);
41         for(int i=0;i<num;i++)
42             scanf("%d",&a[i]);
43 
44 
45         memset(C,0,sizeof(C));
46         for(int i=0;i<num;i++) {
47             add(a[i],1);
48             cc[i]=sum(a[i])-1;//cout<<cc[i]<<endl;
49         }
50         memset(C,0,sizeof(C));
51         for(int i=num-1;i>=0;i--) {
52             add(a[i],1);
53             dd[i]=sum(a[i])-1;//cout<<cc[i]<<endl;
54         }
55         long long ans=0;
56         for(int i=1;i<num-1;i++) {
57             ans+=(cc[i])*(num-(1+i)-dd[i])+
58                  (i-cc[i])*(dd[i]);
59         }
60         cout<<ans<<endl;
61     }
62     return 0;
63 }

//from http://code.google.com/p/aoapc-book/source/browse/TrainingGuide/bookcodes/ch3/la4329.cpp?spec=svn16d535c9811a6d2b26c1fbb2ba40fce4359a4d01&r=16d535c9811a6d2b26c1fbb2ba40fce4359a4d01

inline int lowbit(int x) { return x&-x; }

struct FenwickTree {
  int n;
  vector<int> C;

  void resize(int n) { this->n = n; C.resize(n); }
  void clear() { fill(C.begin(), C.end(), 0); }

  // ¼ÆËãA[1]+A[2]+...+A[x] (x<=n)
  int sum(int x) {
    int ret = 0;
    while(x > 0) {
      ret += C[x]; x -= lowbit(x);
    }
    return ret;
  }

  // A[x] += d (1<=x<=n)
  void add(int x, int d) {
    while(x <= n) {
      C[x] += d; x += lowbit(x);
    }
  }
};

BIT(Binary Indexed Tree)又名 Fenwick Tree

二叉搜索树可以完成这个任务吗？eg use STL/python的set

插入节点，返回比它小的数的个数。