Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4874 Accepted Submission(s): 1777
把运动员排成一排，对于其中任意一个位置i上的人来说，如果他作为裁判，则有这么两种可能：
1.左边的某人能力值低于他，右边高于他；
2.左边的某人能力值高于他，右边低于他。
记左边比他小的人数为l[i]，右边比他小的人数为r[i],
那么左边比他大的人数为i-1-l[i],右边比他大的人数为n-i-r[i]，
则i作为裁判就有l[i]*(n-i-r[i])+(i-1-l[i])*r[i];
前缀 后缀比i人大的数用树状数组求；
那么代码为：
要用long long ；
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<algorithm> 6 //#define LOCAL 7 using namespace std; 8 const int INF=0x3f3f3f3f; 9 const int MAXN=100010; 10 int tree[MAXN+1],a[MAXN],bl[MAXN],br[MAXN]; 11 int lowbit(int x){ 12 return x&(-x); 13 } 14 void update(int x){ 15 while(x<=MAXN){ 16 tree[x]++; 17 x+=lowbit(x); 18 } 19 } 20 int SUM(int x){ 21 int temp=0; 22 while(x){ 23 temp+=tree[x]; 24 x-=lowbit(x); 25 } 26 return temp; 27 } 28 int main(){ 29 #ifdef LOCAL 30 freopen("data.in","r",stdin); 31 freopen("data.out","w",stdout); 32 #endif 33 int T,N; 34 scanf("%d",&T); 35 while(T--){ 36 scanf("%d",&N); 37 for(int i=1;i<=N;i++)scanf("%d",a+i); 38 memset(tree,0,sizeof(tree)); 39 for(int i=1;i<=N;i++){ 40 bl[i]=SUM(a[i]); 41 update(a[i]); 42 } 43 memset(tree,0,sizeof(tree)); 44 for(int i=N;i>0;i--){ 45 br[i]=SUM(a[i]); 46 update(a[i]); 47 } 48 long long ans=0; 49 for(int i=1;i<=N;i++){ 50 ans+=bl[i]*(N-i-br[i])+br[i]*(i-1-bl[i]); 51 } 52 printf("%lld\n",ans); 53 } 54 return 0; 55 }
原文：http://www.cnblogs.com/handsomecui/p/4895949.html