2008 Asia Regional Beijing Ping pong

本文主要是介绍2008 Asia Regional Beijing Ping pong，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Ping pong

题目

样例

思路

树状数组提速，对每一个人当裁判时，计算左小*右大+右小 *左大。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAX_N=100010;
const int maxn=20005;
long long C[MAX_N];
long long a[maxn],b[maxn],d[maxn]; 
int lowbit(int x)
{return x&(-x);
}
int getsum(int x)
{int res=0;for(;x>0;x-=lowbit(x)){res+=C[x];}return res;
}
void change(int x,int c)
{for(;x<=MAX_N;x+=lowbit(x)){C[x]+=c;}
}
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(C,0,sizeof(C));for(int i=1;i<=n;i++){change(a[i],1);b[i]=getsum(a[i]-1);//左小	}memset(C,0,sizeof(C));for(int i=n;i>0;i--){change(a[i],1);d[i]=getsum(a[i]-1);//右小	}long long int sum=0;for(int i=2;i<n;i++)sum+=b[i]*(n-i-d[i])+d[i]*(i-1-b[i]);printf("%lld\n",sum);}return 0;
}

这篇关于2008 Asia Regional Beijing Ping pong的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---