树状数组模板题

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=200005;
int n;
int a[N]; // 表示原数组
int tr[N]; // 表示树状数组
int ga[N]; // 有多少是大于k的
int lo[N]; // 有多少是小于k的

inline int lowbit(int x){return x & -x;}
inline void add(int x, int c){ // 更新
    for(int i=x; i<=n; i+=lowbit(i)) tr[i]+=c;
}
inline int sum(int x){ // 查询
    int ans=0;
    for(int i=x; i; i-=lowbit(i)) ans+=tr[i];
    return ans;
}

int main(){
    memset(a, 0x00, sizeof a);
    memset(tr, 0x00, sizeof tr);
    memset(ga, 0x00, sizeof ga);
    memset(lo, 0x00, sizeof lo);
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];

    for(int i=1; i<=n; ++i){
        int y=a[i];
        ga[i]=sum(n)-sum(y); // y+1到n中有多少个数
        lo[i]=sum(y-1); // 1-y-1中有多少个数
        add(y, 1);
    }

    memset(tr, 0x00, sizeof tr);
    LL ans1=0, ans2=0;

    for(int i=n; i; --i){
        int y=a[i];
        ans1+=ga[i]*(LL)(sum(n)-sum(y));
        ans2+=lo[i]*(LL)(sum(y-1));
        add(y, 1);
    }

    cout<<ans1<<" "<<ans2<<endl;

    return 0;
}