2008年北京的现场赛的题出5了道~~对比下当时的排名..尽然到12名了..至少拿银..囧...或许是这几年ICPC发展太迅猛了吧....
这题如果最暴力的..就是枚举中间的 j ..看左边有多少比 data[j] 小的...右边有多少比 data[j] 大的...相乘加到答案中..再看左边有多少比 data[j] 大的...右边有多少比 data[j] 大的..相乘加到答案中...那么问题关键就是如何在可以接受的时间内得到某位左边有多少个比它小(大)...右边有多少比它大(小)的...
这里可以用两个树状数组来维护...一个记录的是到了k位有多少个比k小的..一个记录到k位有多少个比k大的...那么预处理要知道每位的数是第几大的..我分别用两个数组记录每一位它是第几大和它是第几小..在扫中间数前..两个树状数组都是空的(全0)..边扫边更新两个树状数组..
Program:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
struct node
{
int d,w;
}p[20005];
int n,a[20005],b[20005],s[2][20005];
ll ans;
bool cmp(node a,node b)
{
return a.d<b.d;
}
void insert(int x,int k,int data)
{
while (k<=n)
{
s[x][k]+=data;
k+=(-k)&(k);
}
return;
}
int getsum(int x,int k)
{
int w=0;
while (k>0)
{
w+=s[x][k];
k-=(-k)&(k);
}
return w;
}
int main()
{
int t,i,x;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
p[i].w=i;
scanf("%d",&p[i].d);
}
sort(p+1,p+1+n,cmp);
for (i=1;i<=n;i++) a[p[i].w]=i;
for (i=1;i<=n;i++) b[p[i].w]=n-i+1;
ans=0;
memset(s,0,sizeof(s));
for (i=1;i<=n;i++)
{
x=getsum(0,a[i]);
insert(0,a[i],1);
ans+=x*(n-a[i]-(i-x-1));
x=getsum(1,b[i]);
insert(1,b[i],1);
ans+=x*(n-b[i]-(i-x-1));
}
printf("%I64d\n",ans);
}
return 0;
}