ACM-ICPC LA 4329 Ping pong（树状数组）

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 #define PEOPLE 20001
 5 #define VALUE 100001
 6 
 7 typedef long long LL;
 8 
 9 int n, a[PEOPLE], amin[PEOPLE], amax[PEOPLE], tree[VALUE];
10 
11 
12 int lowbit(int x){
13     return x & -x;
14 }
15 
16 void add(int x, int d){
17     while(x < VALUE){
18         tree[x] += d;
19         x += lowbit(x);
20     }
21 }
22 
23 int sum(int x){
24     int ret = 0;
25     while(x > 0){
26         ret += tree[x];
27         x -= lowbit(x);
28     }
29     return ret;
30 }
31 
32 int main(){
33     int t;
34     scanf("%d", &t);
35     while(t--){
36         scanf("%d", &n);
37         for(int i = 1; i <= n; ++i){
38             scanf("%d", &a[i]);
39         }
40 
41         memset(tree, 0, sizeof(tree));
42         for(int i = 1; i <= n; ++i){
43             amin[i] = sum(a[i] - 1);//第i个人 统计在第i个人的左边并且技能值小于 的总人数
44             amax[i] = i - 1 - amin[i];//统计 技能值大于第i个人并且在左边的总人数
45             add(a[i], 1);
46         }
47 
48         LL ans = 0;
49         memset(tree, 0, sizeof(tree));
50         for(int i = n; i >= 1; --i){
51             LL bmin = sum(a[i] - 1);//统计 技能值小于第i个人并且在第i个人的右边的总人数
52             ans += bmin * amax[i] + (n - i - bmin) * amin[i];
53             add(a[i], 1);
54         }
55         printf("%lld
", ans);
56     }
57     return 0;
58 }