分析

• 因为$y_1$~$y_n$ 是1~n的一个排列，所以不需要进行离散化了；原数组A的下标是$y_1$~$y_n$ 这些数据，数值表示这些数字的个数，非常类似于计数排序的做法。

• 以求解V字形为例，对于我们考察的每个数据$y_i$，我们只要统计出其左侧和其右侧各有多少个数据大于它，然后使用乘法原理就能得到以$y_i$为”山谷”的数量$s_i$，然后将所有的$s_i$相加就是所有V的个数。

• 分析最多有多少答案，对于每个$y_i$，其左右数据够大于它，最坏情况下会有$10^5 \times 10^5 \times 2 \times 10^5=2 \times 10^{15}$个答案，超过int的范围，因此需要使用long long来存储答案。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];  // a[y] = 1; 表示y这个数据有1个
int tr[N];
// Greater[k]表示a[1...k-1]中大于a[k]的数据的数量
// lower[k]表示a[1...k-1]中小于a[k]的数据的数量
int Greater[N], lower[N];

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

// 操作原数组，让a[x] += c;
void add(int x, int c) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] +=c;
}

// 获得a[1...x]的区间和
int sum(int x) {
    int 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("%d", &a[i]);

    for (int i = 1; i <= n; i++) {
        int y = a[i];
        Greater[i] = sum(n) - sum(y);  // 左侧大于y的数的数量
        lower[i] = sum(y - 1);  // 左侧小于y的数的数量
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i--) {
        int y = a[i];
        res1 += Greater[i] * (LL)(sum(n) - sum(y));
        res2 += lower[i] * (LL)(sum(y - 1));
        add(y, 1);
    }

    printf("%lld %lld\n", res1, res2);

    return 0;
}