楼兰图腾 【题解】 树状数组 逆序对

题目链接：https://ac.nowcoder.com/acm/contest/1032/A

（话说CH挂了，可以在牛客上面交）

因为x是按顺序的，那么就是求一个逆序对。

考虑树状数组求逆序对。

两个数组，lt[ ]，rt[ ]。

lt[i]表示 a[i] 前面有几个数比它小。

rt[i]表示 a[i] 后面有几个数比它小，也就是逆序对。

那么" ^ "的数量就是所有 lt[i]*rt[i] 的和。

" v "的数量也一样。

但是实际上不需要再跑一遍。直接用数量减就可以了。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200001;
int n; 
int d[maxn],rt[maxn],a[maxn],lt[maxn];
inline int ask(int x){
    int ans=0;
    for(;x;x-=(x&-x))
        ans+=d[x];
    return ans;
}
inline void add(int x,int y){
    for(;x<=n;x+=(x&-x))
        d[x]+=y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        lt[i]=ask(a[i]);
        add(a[i],1);
    }
    memset(d,0,sizeof(d));
    for(int i=n;i>=1;i--){
        rt[i]=ask(a[i]);
        add(a[i],1);
    }
    ll ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        ans1+=(ll)(i-lt[i]-1)*(n-rt[i]-i);
        ans2+=(ll)lt[i]*rt[i];
    }
    printf("%lld %lld
",ans1,ans2);
    system("pause");
    return 0;
}