分析

对于第i个点，若能知道左边比它小的点的个数m和右边比它小的点的个数n，那么这个点形成 ’^’ 的个数为 m * n

思路

故可以用树状数组维护当前所有数字出现的次数

1、从左向右依次遍历每个数a[i]，找到i点左边比它大以及比它小的点的个数
- add操作 add(a[i], 1) 表明a[i]这个数字出现次数加一
- query操作 query(a[i] - 1) , 表示求 1 到 a[i] - 1 的出现次数的前缀和 等价于 求比a[i]小的点出现了多少次
- 同理 query(n) - query(a[i]), 等价于 求比a[i]大的点出现了多少次

2、从右向左遍历每个数a[i]，找到i点右边比它大以及比它小的点的个数
与第一步的结果相乘得到答案

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
int n;
ll tr[N], a[N];
ll lower[N], higher[N]; // 存储第i个点 lower:左边有多少小于它的点  higher: 左边有多少大于它的点

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

void add(int x, ll d){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

int query(int x){
    ll 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("%lld", &a[i]);

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

    memset(tr, 0, sizeof tr);

    ll resA = 0, resV = 0;
    for(int i = n; i >= 1; --i){
        int x = a[i];
        resA += (lower[i] * query(x - 1));     
        // 由于已经有了左边的值，所以求出右边的大/小的个数后直接相乘即可
        resV += (higher[i] * (query(n) - query(x)));
        add(x, 1);
    }

    cout << resV << " " << resA << endl;

    return 0;
}