题意 一条街上住着一群乒乓球员 每个人的rank都不一样 每两个人可以找一个人做裁判打球 裁判不能比他们rank都低或都高 并且两个人走到裁判家的总路程不能高于两个人的距离
比赛中的三人 任何一个人不同 都是不同的比赛 问最多多少场不同的比赛
也就是说裁判的rank在他们之间 并且家也在两人之间
用树状数组来解答
可知 这条街看作左右向的话 每个人做裁判的场次数相加就是总答案
这个人做裁判的次数=左边比自己弱的人*右边比自己强的人+左边比自己强的人*右边比自己弱的人
由于rank最多是10w 开的下 不用离散化什么的
当输入a[i]的时候（i从1~n）add之前 求一次sum 是这个人左边比自己弱的人
i-1-sum 是这个人左边比自己强的人
然后add
当所有的a[i]都输入并且add完毕后
再对每个a[i]求sum sum-1-这个人左边比自己弱的人=这个人右边比自己弱的人
n-这个人左边比自己弱的人-左边比自己强的人-右边比自己弱的人-1=右边比自己强的人
然后for循环求答案就可以了
需要注意的是最后的ans比较大 int会wa 开long long
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
using namespace std;
int c[100050];
int a[100050];
int xiaoyi[100050];
int xiaoer[100050];
int dayi[100050];
int daer[100050];
int n;
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
for(int i=x;i<=100000;i+=lowbit(i))
{
c[i]++;
}
}
int sum(int x)
{
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int xiaoyiyi=sum(a[i]);
xiaoyi[i]=xiaoyiyi;
add(a[i]);
dayi[i]=(i-1-xiaoyiyi);
}
for(int i=1;i<=n;i++)
{
int xiaozong=sum(a[i]);
xiaoer[i]=(xiaozong-1-xiaoyi[i]);
daer[i]=(n-xiaoyi[i]-xiaoer[i]-1-dayi[i]);
}
long long int ans=0;
for(int i=1;i<=n;i++)
{
ans+=(xiaoyi[i]*daer[i]);
ans+=(xiaoer[i]*dayi[i]);
}
printf("%I64d\n",ans);
}
}
原文：http://www.cnblogs.com/rayrayrainrain/p/5290198.html