题目传送门

Description

小明每天晚上都在数羊。

对于每只羊 $i$ ,都有一个吵闹程度 $a[i]$ ,每只羊的吵闹程度都不同。

小明要数的是对于羊 $(i,j,k (i< j< k))$ 满足 $(a[i]< a[k])$ 而且 $(a[k]<a[j])$ 的羊的 $3$ 元排列 $(i,j,k)$ 组数。

现在小明想请你帮他数这样的羊的组数。

Solution

题目里面需要求 $[1,3,2]$ ,这样太毒瘤了,我们考虑换一种方式。

可以想到, $[1,3,2]=[1,x,x]-[1,2,3]$

而 $[1,x,x]-[1,2,3]$ 都是很好求的。

开 $3$ 个树状数组,边插入边统计就完了。

Code

/*
 * @Name: 110743
 * @Author: Lovely_XianShen
 * @Date: 2019-10-30 19:33:14
 * @Aqours!Sunshine!!
 */

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

inline ll read() {
    ll a = 0; char x = getchar();
    while (x < '0' || x > '9')x = getchar();
    while (x >= '0' && x <= '9')a = (a << 3) + (a << 1) + x - 48, x = getchar();
    return a;
}

const int N = 2e5 + 5;

ll n, a[N], l[N], r[N];
struct xianshen {
    int c[N];
    inline ll lowbit(ll x) {
        return x & (-x);
    }
    inline ll sum(ll x) {
        ll s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x);
        }
        return s;
    }

    inline void add(ll x, ll d) {
        while (x <= n) {
            c[x] += d;
            x += lowbit(x);
        }
    }
    inline void init() {
        memset(c, 0, sizeof c);
    }
} t1, t2, t3;


ll ans1, ans2, ans;
ll pos[N];

ll C2(ll x) {
    return 1ll * x * (x - 1) / 2;
}

int main() {
    n = read();
    t1.init();
    t2.init();
    t3.init();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        pos[a[i]] = i;
        t1.add(a[i], 1);
        l[i] = t1.sum(a[i] - 1);
    }
    for (int i = n; i; i--) {
        t2.add(a[i], 1);
        r[i] = t2.sum(n) - t2.sum(a[i]);
        ans1 += (l[i] * r[i]);
    }
    for (int i = n; i; i--) {
        int x = pos[i];
        ll cnt = t3.sum(n) - t3.sum(x);
        ans2 += C2(cnt);
        t3.add(x, 1);
    }
    cout << ans2 - ans1 << endl;
    return 0;
}