uva 1428 - Ping pong

树状数组,把他们的技能值作为轴;

首先按照编号从小到大插入值,这样就可以得到,技能值比当前小的人数;

然后按照编号从大到小再插一遍;

代码:

 #include<cstdio>
#include<cstring>
#define maxn 20005
using namespace std; int a[maxn],c[];
int l[maxn],r[maxn];
int lowbit(int x){return x&-x;}
void add(int x,int d){while(x<=){c[x]+=d,x+=lowbit(x);}}
int sum(int x)
{
int ret=;
while(x>){ret+=c[x],x-=lowbit(x);}
return ret;
} int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(c,,sizeof c);
memset(l,,sizeof l);
memset(r,,sizeof r);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
add(a[i],);
l[i]=sum(a[i]-);
}
memset(c,,sizeof c);
for(int i=n;i>=;i--)
{
add(a[i],);
r[i]=sum(a[i]-);
}
long long ans=;
for(int i=;i<=n;i++)
ans+=l[i]*(n-i-r[i])+(i-l[i]-)*r[i];
printf("%lld\n",ans);
}
}
上一篇:Cordova webapp实战开发:(2)认识一下Cordova


下一篇:discuz ucenter通信失败