算法
你知道有前面几个数比a[i]小,
那你能直接算出来
后面有几个比他小
前面有几个比它大
后面有几个比它大
根本用不着再查询几次、、
一层for直接写不好嘛、、
时间复杂度(log(n))
C++ 代码
/*author:revolIA*/
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
using namespace std;
typedef long long ll;
const int maxn = 2e5+7;
int n,Tree[maxn];
void Add(int x,int val){
while(x<=n)Tree[x] += val,x += x&-x;
}
int query(int x,int ans = 0){
while(x)ans += Tree[x],x -= x&-x;
return ans;
}
int main(){
scanf("%d",&n);
ll ans1 = 0,ans2 = 0;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
int ldn = query(x);
//查询左边有几个小于x的
int rdn = x-1 - ldn;
ans1 += 1LL*ldn*rdn;
int lup = i-1 - ldn;
int rup = n-x - lup;
ans2 += 1LL*lup*rup;
Add(x,1);
}
printf("%lld %lld\n",ans2,ans1);
return 0;
}