题解

题解传送门

code

#include <bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const int maxn = 2e5 + 100; 

template <typename T>
inline void read(T &s) {
    s = 0; 
    T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
}

int n, sum; 
LL a[maxn], r[maxn], l[maxn], c[maxn]; 

inline LL max(LL aa, LL bb) { return aa > bb ? aa : bb; }
inline LL min(LL aa, LL bb) { return aa < bb ? aa : bb; }
inline int lowbit(int x) { return x & (-x); }

inline void add(int x, LL val) {
    for (; x <= n; x += lowbit(x)) 
        c[x] += val; 
}

inline int query(int x) {
    int ans = 0; 
    for (; x; x -= lowbit(x)) 
        ans += c[x]; 
    return ans; 
}

int main() { 
    read(n); 
    for (int i = 1; i <= n; ++i) {
        read(a[i]); 
        sum = max(sum, a[i]); 
    }

    LL ans = 0; 
    for (int i = n; i >= 1; --i) {
        r[i] += query(sum) - query(a[i]); 
        add(a[i], 1); 
    }
    memset(c, 0, sizeof(c)); 
    for (int i = 1; i <= n; ++i) {
        l[i] += query(sum) - query(a[i]); 
        add(a[i], 1); 
    }
    for (int i = 1; i <= n; ++i) 
        ans += l[i] * r[i]; 
    printf("%lld ", ans); 

    ans = 0;
    memset(r, 0, sizeof(r));  
    memset(l, 0, sizeof(l)); 
    memset(c, 0, sizeof(c)); 

    for (int i = n; i >= 1; --i) {
        r[i] += query(a[i] - 1); 
        add(a[i], 1); 
    }
    memset(c, 0, sizeof(c)); 
    for (int i = 1; i <= n; ++i) {
        l[i] += query(a[i] - 1); 
        add(a[i], 1); 
    }
    for (int i = 1; i <= n; ++i) 
        ans += l[i] * r[i]; 
    printf("%lld", ans); 

    return 0; 
}