Ping pong

OJ题号：LA4329

思路：

树状数组。

参考刘汝佳《训练指南》P197。

　　考虑第$i$个人当裁判的情形。假设$a_1$到$a_{i-1}$中有$c_i$个比$a_i$小，那么就有$(i-1)-c_i$个比$a_i$大；同理，假设$a_{i+1}$到$a_n$中有$d_i$个比$a_i$小，那么就有$(n-i)-d_i$个比$a_i$大。根据乘法原理和加法原理，$i$当裁判有$c_i(n-i-d_i)+(i-c_i-1)d_i$种比赛。这样，问题就转化为求$c_i$和$d_i$。

 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 20001
 4 #define maxa 100001
 5 int t,n,a[maxn],c[maxn],d[maxn];
 6 struct BIT {
 7     int val[maxa];
 8     void reset() {
 9         memset(val,0,sizeof val);
10     }
11     int lowbit(const int x) {
12         return x&-x;
13     }
14     void modify(int p) {
15         while(p<=maxa) {
16             val[p]++;
17             p+=lowbit(p);
18         }
19     }
20     int query(int p) {
21         int ans=0;
22         while(p) {
23             ans+=val[p];
24             p-=lowbit(p);
25         }
26         return ans;
27     }
28 };
29 BIT tree;
30 int main() {
31     scanf("%d",&t);
32     while(t--) {
33         scanf("%d",&n);
34         tree.reset();
35         for(int i=1;i<=n;i++) {
36             scanf("%d",&a[i]);
37             tree.modify(a[i]);
38             c[i]=tree.query(a[i]-1);
39         }
40         tree.reset();
41         for(int i=n;i;i--) {
42             tree.modify(a[i]);
43             d[i]=tree.query(a[i]-1);
44         }
45         long long ans=0;
46         for(int i=1;i<=n;i++) ans+=(long long)c[i]*(n-i-d[i])+(long long)d[i]*(i-1-c[i]);
47         printf("%lld
",ans);
48     }
49     return 0;
50 }