UVA 1428 Ping pong

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 100005;
 7 
 8 int n;
 9 int a[maxn];
10 long long c[maxn];
11 long long l[maxn],r[maxn];
12 
13 int lowbit (int x){
14     return x&(-x);
15 }
16 
17 void add (int x,long long d){
18     while (x<=maxn-5){　　//这里是我坑了很久的地方。。。这里的边界是技能值边界。。。
19         c[x]+=d;
20         x+=lowbit(x);
21     }
22 }
23 
24 long long sum (int x){
25     long long ans=0;
26     while (x>0){
27         ans+=c[x];
28         x-=lowbit(x);
29     }
30     return ans;
31 }
32 
33 int main (){
34     int t;    //while (cin>>t) cout<<lowbit(t)<<endl;
35     cin>>t;
36     while (t--){
37         cin>>n;
38         for (int i=1;i<=n;i++){
39             cin>>a[i];
40         }
41         memset (c,0,sizeof c);
42         for (int i=1;i<=n;i++){
43             l[i]=sum(a[i]);
44             add (a[i],1);
45         }
46         memset (c,0,sizeof c);
47         for (int i=n;i>=1;i--){
48             r[i]=sum(a[i]);
49             add (a[i],1);
50         }
51         long long ans=0;
52         for (int i=1;i<=n;i++)
53             ans+=l[i]*(n-i-r[i])+(i-l[i]-1)*r[i];//cout<<l[i]<<" "<<r[i]<<endl;
54         cout<<ans<<endl;
55     }
56     return 0;
57 }