@zzzc18
2017-09-07T19:46:06.000000Z
字数 951
阅读 1234
UVA
UVALive
其实我们只要利用树状数组就可以知道:某一位置前比它小的数的个数,以及其后比它大的个数,怎么着乘一下就有答案了。
可是我写这个并不是说这个题怎么了,而是关于树状数组,一定要非常注意树状数组的长度究竟是多少,就像本题中,长度不是 而是 ,否则 WA×14 orz
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100000+9;
int a[MAXN];
int n;
int c[MAXN],d[MAXN];
int tree[MAXN];
int lowbit(int x){
return x&-x;
}
void addnum(int pos,int v){
int i;
for(i=pos;i<=100000;i+=lowbit(i))
tree[i]+=v;
}
int getsum(int pos){
int i;
int re=0;
for(i=pos;i>=1;i-=lowbit(i))
re+=tree[i];
return re;
}
void solve1(){
int i;
for(i=1;i<=100000;i++)
tree[i]=0;
for(i=1;i<=n;i++){
addnum(a[i],1);
c[i]=getsum(a[i]-1);
}
for(i=1;i<=100000;i++)
tree[i]=0;
for(i=n;i>=1;i--){
addnum(a[i],1);
d[i]=getsum(a[i]-1);
}
}
void solve2(){
int i;
LL ans=0;
for(i=1;i<=n;i++){
ans+=(LL)c[i]*(n-i-d[i]);
ans+=(LL)(i-c[i]-1)*d[i];
}
printf("%lld\n",ans);
}
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
solve1();
solve2();
}
return 0;
}