LA 4329 ping-pong树状数组

题目链接：

刘汝佳，大白书，P197.

枚举裁判的位置，当裁判为i时，可以有多少种选法，如果已经知道在位置i之前有ci个数比ai小，那么在位置i之前就有i-1-ci个数比ai大。

在位置i之后有di个数比ai小，那么在位置i之后就有n-i-di个数比ai大。

这样，选法数有ci*(n-i-di)+di*(i-1-ci).

注意到ai的值各不相同且ai的值最大不超过10^5，那样就可以用v[a[i]]表示a[i]是否已经存在，这样当顺时针扫描的时候，每次更新v[a[i]] = 1;//表示已经存在。

比ai小的数的个数就是sum(v[j]) j<a[i].

至于d[i]的求法逆着扫描即可，如果用树状数组加速。

贴代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 typedef long long int ll;
 6 const int N1 =20004,N2 = 100005;
 7 int a[N1],c[N2],sum[N1];
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 void add(int index,int value)
13 {
14     while(index < N2)
15     {
16         c[index] += value;
17         index += lowbit(index);
18     }
19 }
20 int getSum(int index)
21 {
22     int s =0;
23     while(index)
24     {
25         s += c[index];
26         index -= lowbit(index);
27     }
28     return s;
29 }
30 int main()
31 {
32 //    freopen("in.txt","r",stdin);
33     int T,n;
34     scanf("%d",&T);
35     while(T--)
36     {
37         scanf("%d",&n);
38         for(int i=1; i<=n; ++i)
39             scanf("%d",&a[i]);
40         memset(c,0,sizeof(c));
41         for(int i=1; i<=n; ++i)
42         {
43             add(a[i],1);
44             sum[i] = getSum(a[i]-1);
45         }
46         memset(c,0,sizeof(c));
47         ll ans =0;
48         for(int i=n; i>0; --i)
49         {
50             add(a[i],1);
51             int tmp = getSum(a[i]-1);
52             ans += (ll)sum[i]*(n-i-tmp) + (ll)(i-1-sum[i])*tmp;
53         }
54         cout<<ans<<endl;
55     }
56     return 0;
57 }

View Code

注意，如果想输出long long int 用printf（）函数WA了的话，就考虑一下cout吧····