题目不难,用权值线段树维护逆序对.
用树状数组也可解.常数更小
#include <cstdio>
#include <cstdlib>
using namespace std;
#define MAX(a,b) (a>b?a:b)
typedef long long ll;
const int N = 200000+5;
int tree[N<<2];
void add(int l,int r,int rt,int p){
tree[rt] += 1;
int mid = l+r>>1;
if(l==r){
return;
}
if(p <= mid){
add(l,mid,rt<<1,p);
}else{
add(mid+1,r,rt<<1|1,p);
}
}
int query_less(int l,int r,int rt,int p){ // 查询区间内有多少个比p小的
if(p <= l){
return 0;
}else if(p > r){
return tree[rt];
}else{
int ans = 0;
int mid = l+r>>1;
ans += query_less(l,mid,rt<<1,p);
if(p > mid+1){
ans += query_less(mid+1,r,rt<<1|1,p);
}
return ans;
}
}
int left_less[N];
int main(){
int n,temp;
ll up = 0,down = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",&temp);
add(1,n,1,temp);
ll left_less = query_less(1,n,1,temp); // 左侧有多少个比其小的
up += (ll)left_less * (ll)(temp-1-left_less);
down += (ll)(i-1-left_less)*(ll)(n-temp-i+1+left_less);
}
printf("%lld %lld",down,up);
return 0;
}