poj 3928 ping pong 树状数组

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<math.h>
 6 #define maxx 100002
 7 using namespace std;
 8 int a[20022],c[100022],x[100022],n,zuo[100022],you[100022];
 9 
10 int lowbit(int x)
11  {
12      return x&(-x);
13  }
14 
15  __int64 sum(int p)
16  {
17      __int64 ans=0;
18      while(p>0)
19      {
20          ans+=c[p];//printf("i %d   c %d  ans %d\n",p,c[p],ans);
21          p-=lowbit(p);
22      }
23      return ans;
24  }
25 
26  void update(int p)
27  {
28      while(p<=100010)       //!!!!!!!!!!!!!!!!不是p<=n
29      {
30          c[p]++;
31          p+=lowbit(p);
32      }
33 
34  }
35 int main()
36 {
37     int i,j,m,t;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%d",&n);
42         for(i=1;i<=n;i++)
43             scanf("%d",&a[i]);
44 
45         memset(c,0,sizeof(c));
46         for(i=1;i<=n;i++)
47         {
48             zuo[i]=sum(a[i]);
49             update(a[i]);
50         }
51 
52         memset(c,0,sizeof(c));
53         for(i=n;i>=1;i--)
54         {
55             you[i]=sum(a[i]);
56             update(a[i]);
57         }
58         long long final=0;
59         for(i=1;i<=n;i++)
60         {
61             final+=(zuo[i]*(n-i-you[i]))+(you[i]*(i-zuo[i]-1));
62         }
63         printf("%lld\n",final);
64     }
65     return 0;
66 }