[数据结构与算法]241. 楼兰图腾 （逆序对 树状数组

添加链接描述

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+9;
int arr[N];
int mx0[N],tr[N],mx1[N];
int mi0[N],mi1[N];
int lowbit(int x){
    return x&-x;
}
int query(int x){
    int ans=0;
    for(;x;x-=lowbit(x)){
        ans+=tr[x];
    }
    return ans;
}
void modify(int x,int y){
    for(;x<N;x+=lowbit(x)){
        tr[x]+=y;
    }
}
signed main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        arr[i]=x;
        mi0[i]=query(x);
        mx1[i]=query(N-1)-query(x);
        // cout<<i<<" "<<sum0[i]<<" "<<sum1[i]<<"\n";
        modify(x,1);
   }
//    cout<<ans<<endl;
    memset(tr,0,sizeof tr);
    for(int i=n;i;i--){
        int x=arr[i];
        mi1[i]=query(x);
        mx0[i]=query(N-1)-query(x);
        modify(x,1);
    }
    int ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        ans1+=mx0[i]*mx1[i];
        ans2+=mi0[i]*mi1[i];
        // cout<<mx0[i]<<" "<<mx1[i]<<endl;
    }
    cout<<ans1<<" "<<ans2<<endl;

    return 0;
}