AcWing 241. 楼兰图腾
原题链接
简单
作者:
成为一个优秀的人
,
2021-10-28 14:33:46
,
所有人可见
,
阅读 253
通过树状数组求前面比当前数小的数的个数,进而求出前大,后小和后大。
V图腾 = qh * hh
^图腾 = ql * hl
#include<iostream>
using namespace std;
#define lowbit(x) (x & (-x))
const int N = 2E5 + 5;
typedef long long ll;
int n;
ll tree[N];
ll v1, v2;
struct Node{
ll val;a
int id;
}B[N];
inline void update(int i, int x){
for(int pos = i; pos <= n; pos += lowbit(pos)) tree[pos] += x;
}
inline ll query(int i){
ll ans = 0;
for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[pos];
return ans;
}
int main(){
cin>>n;
for(int i = 1; i <= n; i ++ ){
cin>>B[i].val;
B[i].id = i;
}
for(int i = 1; i <= n; i ++ ){
ll ql = query(B[i].val); //前面小的
ll qh = B[i].id - 1 - ql; //前面大的
ll hl = B[i].val - 1 - ql; //后面小的
ll hh = n - ql - qh - hl - 1; //后面大的
v1 += qh * hh;
v2 += ql * hl;
update(B[i].val, 1);
}
printf("%lld %lld", v1, v2);
return 0;
}