于是这篇文章又接上了上一篇讲LIS的

又是一道维护线性具有单调性的序列的题，我们这次又双用上我们的$\log n$数据结构——树状数组。

很明显，对于每个节点$i$（$1<i<n$），我们需要维护的就是两端比它大（或小）的数据的个数，这里用上树状数组，可以将插入的时间复杂度降低到$\log n$，可以显著优化此类需要频繁插入数据的情况。

#include <bits/stdc++.h>
#define MAXN 200001
using namespace std;
using ll = long long;

int n;

ll tree[MAXN];
ll ys[MAXN];
ll l[MAXN],r[MAXN];

ll ansa,ansb;

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

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

ll query(int x) {
    ll ret = 0;
    for (int i = x; i; i -= lowbit(i))
        ret += tree[i];

    return ret;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> ys[i];

    for (int i = 1; i <= n; ++i) {
        l[i] = query(ys[i]);
        add(ys[i]);
    }

    memset(tree, 0, sizeof(tree));

    for (int i = n; i >= 1; --i) {
        r[i] = query(ys[i]);
        add(ys[i]);
    }

    for (int i = 2; i < n ; ++i) {
        ansa += (i - l[i] -1) * (n - i - r[i]);
        ansb += l[i] * r[i];
    }

    cout << ansa << ' ' << ansb << endl;

    return 0;
}