241. 楼兰图腾
分别统计i位置左边比a[i]小的数的个数m、右边比a[i]小的数的个数n,运用乘法原理:
1. 第一步从左边m个数中任选一个,有m种选法
2. 第二步从右边n个数中任选一个,有n种选法
权值树状数组,统计比自己大的和。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int c[200005], a[200005], n, h[200005], l[200005];
ll res, ans;
int lowbit(int x){
return x & (-x);
}
void add(int i, int x){
for(; i <= n; i += lowbit(i))
c[i] += x;
}
int sum(int i){
int sm = 0;
for(; i; i -= lowbit(i))
sm += c[i];
return sm;
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= n; i++){
h[i] = sum(n) - sum(a[i]);
l[i] = sum(a[i]-1);
add(a[i], 1);
}
memset(c, 0, sizeof c);
for(int i = n; i >= 1; i--){
ans += 1ll * h[i] * (sum(n) - sum(a[i]));
res += 1ll * l[i] * sum(a[i]-1);
add(a[i], 1);
}
printf("%lld %lld",ans, res);
return 0;
}
标签:200005,树状,int,res,sum,数组,ans,include From: https://www.cnblogs.com/caterpillor/p/16637518.html