题解

我是线段树玩家，所以我就用线段树了。

思路就不再阐释了，别的题解都很清楚，这里仅仅给线段树没过的同学参考一下。

时间复杂度 $O(n\log n)$。

代码

#include<bits/stdc++.h>

#define ll long long
#define y1 caibictq
#define P pair<int, int>
#define fi first
#define se second

using namespace std;

const int MAXN = 200010;
const int MAXM = 100010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int n, m, k;
ll tot, cnt, ans1, ans2;

int read() {
    int f = 1, s = 0;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 1) + (s << 3) + ((int)ch ^ 48); ch = getchar();}
    return s * f;
}

int a[MAXN], b[MAXN];

struct Segment_Tree {
    int l[MAXN << 2], r[MAXN << 2];
    int sum[MAXN << 2], tag[MAXN << 2];
    void update(int p) {
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
        return;
    }
    void Build_Tree(int p, int x, int y) {
        l[p] = x; r[p] = y;
        if (x == y) {
            sum[p] = tag[p] = 0;
            return;
        }
        int mid = (x + y) >> 1;
        Build_Tree(p << 1, x, mid);
        Build_Tree(p << 1 | 1, mid + 1, y);
        update(p);
        return;
    }
    void pushdown(int p) {
        if (tag[p]) {
            sum[p << 1] += tag[p] * (r[p << 1] - l[p << 1] + 1);
            sum[p << 1 | 1] += tag[p] * (r[p << 1 | 1] - l[p << 1 | 1] + 1);
            tag[p << 1] += tag[p];
            tag[p << 1 | 1] += tag[p];
            tag[p] = 0;
        }
        return;
    }
    void Modify(int p, int x, int y, int k) {
        if (x <= l[p] && r[p] <= y) {
            sum[p] += k * (r[p] - l[p] + 1);
            tag[p] += k;
            return;
        }
        pushdown(p);
        int mid = (l[p] + r[p]) >> 1;
        if (x <= mid) Modify(p << 1, x, y, k);
        if (mid < y) Modify(p << 1 | 1, x, y, k);
        update(p);
        return;
    }
    int Query(int p, int x, int y) {
        if (x <= l[p] && r[p] <= y) {
            return sum[p];
        }
        pushdown(p);
        int mid = (l[p] + r[p]) >> 1;
        int res = 0;
        if (x <= mid) res += Query(p << 1, x, y);
        if (mid < y) res += Query(p << 1 | 1, x, y);
        return res;
    }
}SGT1, SGT2;

int main() {
    int T;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    SGT1.Build_Tree(1, 1, n);
    SGT2.Build_Tree(1, 1, n);
    SGT1.Modify(1, a[1], a[1], 1);
    for (int i = 3; i <= n; i++) {
        SGT2.Modify(1, a[i], a[i], 1);
    }
    for (int i = 2; i < n; i++) {
        int res1 = SGT1.Query(1, 1, a[i] - 1);
        int res2 = SGT2.Query(1, 1, a[i] - 1);
        ans1 += (ll)(i - 1 - res1) * (n - i - res2);
        ans2 += (ll)res1 * res2;
        SGT1.Modify(1, a[i], a[i], 1);
        SGT2.Modify(1, a[i + 1], a[i + 1], -1); 
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}