楼兰图腾

这个题貌似就是让你找逆序对?emm...没啥好说的.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll sum[N];//建树
ll a[N],n;
ll Greater[N];//左边比它大的数.
ll Less[N];//左边比它小的数.
int lowbit(int x)
{
    return x&(-x);
}

void insert(int pos,int val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    ll res=0;
    while(pos>0)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main()
{
    ll ans1=0,ans2=0;
    int x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        Greater[i]=query(n)-query(a[i]);
        Less[i]=query(a[i]-1);
        insert(a[i],1);
    }
    memset(sum,0,sizeof sum);
    for(int i=n;i>=1;i--)
    {
        ans1+=Greater[i]*(query(n)-query(a[i]));
        ans2+=Less[i]*(query(a[i]));
        insert(a[i],1);
    }
    cout<<ans1<<' '<<ans2<<endl;
    return 0;
}