题解 | #楼兰图腾#

思路："V"图案就是对于每一个数，找左边比他大的数设为L,右边比他大的数 R ,"V"图案的个数就应该是 L*R，
"^" 图案就是找左边比他小的数，右边比他小的数的个数，相乘。
而这个找左边比它小的数，右边比他小的数，相信做过逆序对那题都知道怎么做。用树状数组就可以了。
这一题题目已经说明了是一个全排列，所以连离散化都不需要了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,a[1000010],c[1000010];//a原数组，c差分数组
int great[N];
inline int lowbit(int x){return x&-x;}

void updata(int i,int k){
    for(;i<=n;i+=lowbit(i)) c[i]+=k;
}

int getsum(int i){
    int ans=0;
    for(;i>0;i-=lowbit(i)) ans+=c[i];
    return ans;
}


int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        great[i]=i-getsum(a[i]);
        updata(a[i],1);
    }
    memset(c,0,sizeof c);
    long long res1=0,res2=0;
    for(int i=n-1;i>=0;i--){
        int lower=getsum(a[i]);
        res1+=(n-1ll-i-lower)*great[i];
        res2+=lower*1ll*(i-great[i]);
        updata(a[i],1);
    }
    cout<<res1<<" "<<res2<<endl;
    return 0;
}