LA 4329 (树状数组) Ping pong

浏览数：32 / 时间：2015年06月08日

第一次写树状数组，感觉那个lowbit位运算用的相当厉害。

因为-x相当于把x的二进制位取反然后整体再加上1，所以最右边的一个1以及末尾的0，取反加一以后不变。

比如1000取反是0111加一得到1000，这样与运算以后不变

最右边的1左边部分取反，加一不会影响左半部分，所以与运算以后全部为0

对于这道题来说貌似不是很容易能联想到树状数组

注意题中说了每个人的技能值互不相同。

从左往右扫描每个a[i]，另x[a[i]] = 1，然后统计x[1]...x[a[i]-1]的和就是第i个人左边技能值比他小的人数c[i]，所以第i个人左边技能值比他大的人数就是i-1-c[i]

同样地，从右往左扫描a[i]，也另x[a[i]] = 1，统计x[1]...x[a[i]-1]的和就是这个人右边技能值比他小的人数d[i]，所以他右边技能值比他大的人数就是n-i-d[i]

在根据计数原理，求一下总的方案数就是sum{ c[i] * n-i-d[i] + d[i] * i-1-c[i] }

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 inline int lowbit(int x) { return x & (-x); }
 7 
 8 struct Fenwicktree
 9 {
10     int n;
11     vector<int> C;
12 
13     void resize(int n) { this->n = n; C.resize(n); }
14     void clear() { fill(C.begin(), C.end(), 0); }
15 
16     int sum(int x)
17     {
18         int ret = 0;
19         while(x)
20         {
21             ret += C[x];
22             x -= lowbit(x);
23         }
24         return ret;
25     }
26 
27     void add(int x, int d)
28     {
29         while(x <= n)
30         {
31             C[x] += d;
32             x += lowbit(x);
33         }
34     }
35 }f;
36 
37 const int maxn = 20000 + 10;
38 int a[maxn], c[maxn], d[maxn];
39 
40 int main()
41 {
42     //freopen("in.txt", "r", stdin);
43 
44     int T;
45     scanf("%d", &T);
46     while(T--)
47     {
48         int n, maxa = 0;
49         scanf("%d", &n);
50         for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxa = max(maxa, a[i]); }
51         f.resize(maxa); f.clear();
52         for(int i = 1; i <= n; i++)
53         {
54             f.add(a[i], 1);
55             c[i] = f.sum(a[i] - 1);
56         }
57         f.clear();
58         for(int i = n; i > 0; i--)
59         {
60             f.add(a[i], 1);
61             d[i] = f.sum(a[i] - 1);
62         }
63         long long ans = 0;
64         for(int i = 1; i <= n; i++) ans += (long long)c[i]*(n-i-d[i]) + (long long)d[i]*(i-1-c[i]);
65         printf("%lld\n", ans);
66     }
67 
68     return 0;
69 }