POJ 3928

树状数组的应用。

把每个人当做裁判进行遍历，计算住在这个人之前的人中有多少个是比他弱的，记为pre_less[i],多少个人比他强的记为pre_more[i];同样的，住在他后面的人中，比他弱的记为suf_less[i],比他强的记为suf_more[i]

那么，很显然的对于每个裁判judger[i]，可以进行pre_less[i]*suf_more[i]+pre_more[i]+suf_less[i]场比赛，累加起来即得答案。

 1 #include<cstdio>
 2 #define MAX_N 20000+5
 3 int n,a[MAX_N],c[100000+5],MAX_ai;
 4 int pre_more[MAX_N],pre_less[MAX_N],suf_more[MAX_N],suf_less[MAX_N];
 5 long long ans;
 6 int lowbit(int x){return x&(-x);}
 7 void add(int i,int val)
 8 {
 9     while(i<=MAX_ai)
10     {
11         c[i]+=val;
12         i+=lowbit(i);
13     }
14 }
15 int sum(int i)
16 {
17     int s=0;
18     while(i>0)
19     {
20         s+=c[i];
21         i-=lowbit(i);
22     }
23     return s;
24 }
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d",&n);
32         MAX_ai=0;
33         for(int i=1;i<=n;i++)
34         {
35             scanf("%d",&a[i]);
36             if(MAX_ai<a[i]) MAX_ai=a[i];
37         }
38         for(int i=1;i<=n;i++) pre_more[i]=0,pre_less[i]=0,suf_more[i]=0,suf_less[i]=0;
39         for(int i=1;i<=MAX_ai;i++) c[i]=0;
40         for(int i=1;i<=n;i++)
41         {
42             add(a[i],1);
43             pre_less[i]=sum(a[i]-1);
44             pre_more[i]=i-1-pre_less[i];
45         }
46         for(int i=1;i<=MAX_ai;i++) c[i]=0;
47         for(int i=n;i>=1;i--)
48         {
49             add(a[i],1);
50             suf_more[i]=sum(MAX_ai)-sum(a[i]);
51             suf_less[i]=n-i-suf_more[i];
52         }
53         ans=0;
54         for(int i=1;i<=n;i++)
55         {
56             ans+=pre_less[i]*suf_more[i]+pre_more[i]*suf_less[i];
57         }
58         printf("%I64d
",ans);
59     }
60 }

当然，从代码中不难看出，有两个数组是不必要开的，pre_more[]和suf_less[]是根据pre_less[]和suf_more[]算出来的，那么我们完全可以在最后运算时再计算……

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAX_N 20000+5
 4 int n,a[MAX_N],c[100000+5],MAX_ai;
 5 int pre_less[MAX_N],suf_more[MAX_N];
 6 int lowbit(int x){return x&(-x);}
 7 void add(int i,int val)
 8 {
 9     while(i<=MAX_ai)
10     {
11         c[i]+=val;
12         i+=lowbit(i);
13     }
14 }
15 int sum(int i)
16 {
17     int s=0;
18     while(i>0)
19     {
20         s+=c[i];
21         i-=lowbit(i);
22     }
23     return s;
24 }
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d",&n);
32         MAX_ai=0;
33         for(int i=1;i<=n;i++)
34         {
35             scanf("%d",&a[i]);
36             if(MAX_ai<a[i]) MAX_ai=a[i];
37         }
38         for(int i=1;i<=n;i++) pre_less[i]=0,suf_more[i]=0;
39         for(int i=1;i<=MAX_ai;i++) c[i]=0;
40         for(int i=1;i<=n;i++)
41         {
42             add(a[i],1);
43             pre_less[i]=sum(a[i]-1);
44         }
45         for(int i=1;i<=MAX_ai;i++) c[i]=0;
46         for(int i=n;i>=1;i--)
47         {
48             add(a[i],1);
49             suf_more[i]=sum(MAX_ai)-sum(a[i]);
50         }
51         long long ans=0;
52         for(int i=2;i<=n-1;i++)
53         {
54             ans+=pre_less[i]*suf_more[i]+(i-1-pre_less[i])*(n-i-suf_more[i]);
55         }
56         printf("%I64d
",ans);
57     }
58 }

不难看到，程序在各方面都得到了小幅优化