AcWing 241. 楼兰图腾 （树状数组）打卡

题目：https://www.acwing.com/problem/content/description/243/

题意：给你n个点，问你 V 和  ^的图腾有多少个

思路：比如V 其实就是找当前点左边比自己大的点的个数，右边比自己大的个数，然后乘法原理组合一下，^也是一样的道理

#include<bits/stdc++.h>
#define maxn 200005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll c[maxn];
ll l1[maxn],r1[maxn];
ll l2[maxn],r2[maxn];
ll a[maxn],n;
ll lowbit(ll x){
    return x&(-x);
} 
void add(ll x,ll y){
    while(x<=n){
        c[x]+=y;
        x+=lowbit(x);
    }
}
ll sum(ll x){
    ll num=0;
    while(x){
        num+=c[x];
        x-=lowbit(x);
    }
    return num;
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        l1[i]=sum(a[i]);
        l2[i]=i-l1[i]-1;
        add(a[i],1);
    }
    memset(c,0,sizeof(c));
    for(int i=n;i>=1;i--){
        r1[i]=sum(a[i]);
        r2[i]=n-i-r1[i];
        add(a[i],1);
    }
    ll num1=0,num2=0;
    for(int i=1;i<=n;i++){
        num2+=l1[i]*r1[i];
        num1+=l2[i]*r2[i];
    }
    printf("%lld %lld",num1,num2);
}