hdu 2492 Ping pong[树状数组]

题意：(1 <= ai <= 100000，3<=N<=20000)

n个人每个人有个技术值ai，只要三个人中间（位置中间）那个人的技术值在其他两个人中间，他就能成为裁判，并可举办一场比赛，求能举办多少次比赛。

题解：枚举每个人做裁判，用树状数组存每个技术值出现的人数，计算位置在裁判前，比裁判技术值小的人数b[i] 和位置在裁判后面，比裁判技术值小的人数c[i]，第i个人做裁判能举办的比赛场数即为b[i] * (n-i–c[i]) + c[i] * (i-1-b[i])

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 const int N = 2e4+5;
 9 int tree[100005];
10 int a[N];
11 int b[N], c[N];//第i人前比他分小的数量，，第i人后比他分小数量
12 int n, m;
13 int lowbit(int x){
14     return x&(-x);
15 }
16 void add(int i){
17     while(i <= m){
18         tree[i]++;
19         i += lowbit(i);
20     }
21 }
22 int query_sum(int i){
23     int sum = 0;
24     while(i){
25         sum += tree[i];
26         i -= lowbit(i);
27     }
28     return sum;
29 }
30 int main() {
31     int i, t;
32     scanf("%d", &t);
33     while(t--) {
34         memset(tree, 0, sizeof(tree));
35         scanf("%d", &n);
36         m = 0;
37         for(i = 1; i <= n; ++i) {
38             scanf("%d", &a[i]);
39             m = max(m, a[i]);
40         }
41         for(i = 1; i <= n; ++i) {
42             add(a[i]);
43             b[i] = query_sum(a[i]-1);
44         }
45         memset(tree, 0, sizeof(tree));
46         for(i = n; i >= 1; --i) {
47             add(a[i]);
48             c[i] = query_sum(a[i]-1);
49         }
50         ll ans = 0;
51         for(i = 2; i <= n-1; ++i)
52             ans += b[i] * (n-i-c[i]) + c[i] * (i-b[i]-1);
53         printf("%lld
", ans);
54     }
55     return 0;
56 }

View Code