楼兰图腾（树状数组的板子题）

#include<iostream>
#include<cstring>
using namespace std;

const int N = 200010;
int tr[N],a[N];
int lower[N],higher[N];
typedef long long ll;
int n;
//维护节点
int lowbit(int x)
{
    return x & -x;
}
void add(int x)
{
    for(int i = x;i <= n;i += lowbit(i))tr[i] ++;
}
int Sum(int x)
{
    int res = 0;
    for(int i = x;i;i -=lowbit(i))res += tr[i];
    return res;
}


int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)scanf("%d",&a[i]);

    for(int i = 1;i <= n;i ++)
    {
        int y = a[i];
        lower[i] = Sum(y - 1);
        higher[i] = Sum(n) - Sum(y);
        add(y);
    }

    memset(tr,0,sizeof tr);
    ll res1 = 0,res2 = 0;


    for(int i = n;i;i--)
    {
        int y = a[i];
        res1 += (ll)lower[i] * Sum(y - 1);//现在的sum(y - 1)是统计的是比他高的
        res2 += (ll)higher[i] * (Sum(n) - Sum(y));//sum(n) - sum(y)统计的是比它低的(y - n)
        add(y);
    }
    cout<<res2<<" "<<res1<<endl;

}