「TYVJ1432」楼兰图腾

题目中说明了 $y_1 \thicksim y_n$ 是的一个排列，我们把这 $N$ 个点按照横坐标排序后的纵坐标排列记为 $a$。

根据题意要找的图腾这样是，很明显可以看出要我们求逆序对。

在求逆序对中，我们可以求得一个序列中每个数后面有多少个数比它小，类似地，我们可以：

1.倒序扫描序列a，利用树状数组求出每个 $a[i]$ 后边有几个数比它大，记为 $right[i]$；

2.正序扫描序列a，利用树状数组求出每个 $a[i]$ 前边有几个数比它大，记为 $left[i]$。

依次枚举每个点作为中心点，以该点为中心的“$\bigvee$”字图腾个数显然是 $left[i]*right[i]$，所以”$\bigvee$”字图腾的总数就是 $\sum^N_{i=1}left[i]∗right[i]$。

按照同样的方法，我们可以统计出另外一个图腾的个数。

#include<stdio.h>
#include<string.h>
long long n,tree[201010],y[201010];
long long lmin[201010],lmax[201010];
long long rmin[201010],rmax[201010];
long long lowbit(long long x)
{
    return x&(-x);
}
void update(long long x,long long val)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tree[i]+=val;
}
long long ask(long long x)
{
    long long ans=0;
    for(int i=x;i;i-=lowbit(i))
        ans+=tree[i];
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&y[i]);
        lmin[i]=ask(y[i]);
        lmax[i]=i-lmin[i]-1;
        update(y[i],1);
    }
    memset(tree,0,sizeof(tree));
    for(int i=n;i;i--)
    {
        rmin[i]=ask(y[i]);
        rmax[i]=n-rmin[i]-i;
        update(y[i],1);
    }
    long long ans1=0,ans2=0;
    for(int i=1;i<=n;i++)
    {
        ans1+=lmax[i]*rmax[i];
        ans2+=lmin[i]*rmin[i];
    }
    printf("%lld %lld",ans1,ans2);
    return 0;
}