题目链接:点击进入 开始的时候想着枚举两个比赛的选手,然后再求在他们中间有多少个满足要求的裁判,但是这样时间复杂度就不可能满足题目的要求.后面觉得可以枚举每个人做裁判的情况;假设第i位选手做裁判,然后设其左边1–i-1中有lmin[i]个人的排名比他低,则有i-1-lmin[i]个人的排名不比他低,设其右边i+1–n中有rmin[i]个人的排名比他低,则有n-i-rmin[i]个人的排名不比他低.则第i位选手做裁判时,可以举行的比赛数为lmin[i](n-i-rmin[i])+rmin[i](i-1-lmin[i])。所以现在的问题在于求出每位选手左右的rmin和lmin。 在这里我们可以假定有一个排名数组c[]，，其中c[i]=x表示有x个人处于第i名的位置。然后现在我们要求第i位选手左边有多少个人的排名比它的低；我们可以将它左边的所有选手的排名都插入这个数组中，然后查询c[1]+c[2]+…+c[a[i]-1]的值就行了。所以我们只要对所有选手从左到右进行查询和更新就行了，这里可以用线段树或是树状数组实现。对于每个选手右边的情况也可以类似处理。
代码如下：
;a[maxn],C[maxn*4],m;int lmin[maxn],rmin[maxn];int lowbit(int x){return x&(-x);}int sum(int x){int ret=0;while(x>0){ret+=C[x];x-=lowbit(x);}return ret;}void add(int x,int d){while(x<=m){C[x]+=d;x+=lowbit(x);}}int main(){//freopen(“in.txt”,”r”,stdin);int t;scanf(“%d”,&t);while(t–){int n;m=0;scanf(“%d”,&n);for(int i=1;i<=n;i++){scanf(“%d”,&a[i]);m=max(m,a[i]);}memset(C,0,sizeof(C));memset(lmin,0,sizeof(lmin));memset(rmin,0,sizeof(rmin));for(int i=1;i<=n;i++){lmin[i]=sum(a[i]-1);add(a[i],1);}memset(C,0,sizeof(C));for(int j=n;j>=1;j–){rmin[j]=sum(a[j]-1);add(a[j],1);}ll ans=0;for(int i=2;i<n;i++){ans+=(ll)lmin[i]*(n-i-rmin[i]);ans+=(ll)rmin[i]*(i-1-lmin[i]);}printf(“%lld\n”,ans);} return 0;}
一切都在发展变化，不断地向昨天告别，满怀信心地投入每一个崭新的今天。
