楼兰图腾

题目链接

题意很清晰，抽象一下的话就是求每个数左边和右边比它小的数能组成几个'v'型序列，每个数左边和右边比它大的数能组成几个'^'型序，利用树状数组正向和反向求一边这个数左边比它小(大)和右边比它小(大)的数，然后按照排列组合求出每个数可以得到几个'V'和 ' ^ '即可，跟求逆序对差不多

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 200005;

ll tree[maxn],premax[maxn],premin[maxn];
ll a[maxn];
int n;

inline ll lowbit(int x)
{
    return x & (-x);
}

void add(int x,int c)
{
    for(int i = x; i <= n; i += lowbit(i))  tree[i] += c;  
}

ll Query(int x)
{
    ll res = 0;
    for(int i = x; i > 0; i -= lowbit(i))  res += tree[i];
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 1; i<= n; i++) cin>>a[i];
    //求每个数前面有几个比当前数大或者小
    for(int i = 1; i <= n; i++ ){
        int t = a[i];
        premax[i] = Query(n) - Query(t);
        premin[i]  = Query(t - 1);
        add(t,1);
    }
    ll ans1 = 0,ans2 = 0;
    memset(tree , 0 ,sizeof tree);
    //求每个数后面有几个比它自己大或者小的并乘上前面比它大或者小的数
    for(int i = n; i > 0; i--){
        int t = a[i];
        //求 'v' 数量
        ans1 += premax[i] * (Query(n) - Query(t));
        //求 '^' 数量
        ans2 += premin[i] * Query(t - 1);
        add(t,1);
    }
    cout<<ans1<<' '<<ans2<<endl;
    return 0;
}