AcWing 241. 楼兰图腾
原题链接
简单
作者:
fancywing
,
2021-01-19 17:33:05
,
所有人可见
,
阅读 302
树状数组模板题
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
typedef long long LL;
int n, a[N];
LL t[N], r[N], l[N];
int lowbit(int x){
return x & -x;
}
void add(int i, int x){
while(i <= n){
t[i] += x;
i += lowbit(i);
}
}
int query(int i){
int res = 0;
while(i){
res += t[i];
i -= lowbit(i);
}
return res;
}
int main(){
cin>>n;
for(int i = 1; i<=n; i++) cin >> a[i];
LL sumA = 0, sumV = 0;
// 统计右侧比a[i]大的个数
for(int i = n; i >=1; i--){
r[i] = query(n) - query(a[i]);
add(a[i], 1);
}
// 统计左侧比a[i]大的个数
memset(t, 0, sizeof(t));
for(int i = 1; i <= n; i++){
l[i] = query(n) - query(a[i]);
add(a[i], 1);
}
for(int i = 1; i <= n; i++){
sumV += l[i] * r[i];
}
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
// 统计右侧比a[i]小的个数
memset(t, 0, sizeof(t));
for(int i = n; i >=1; i--){
r[i] = query(a[i] - 1);
add(a[i], 1);
}
// 统计左侧比a[i]小的个数
memset(t, 0, sizeof(t));
for(int i = 1; i <= n; i++){
l[i] = query(a[i] - 1);
add(a[i], 1);
}
for(int i = 1; i <= n; i++){
sumA += l[i] * r[i];
}
cout<< sumV << " "<<sumA<<endl;
return 0;
}