给定长度为 $n$ 的数列 $a$，求满足以下条件的三元组 $(i,j,k)$ 数量：

• $1 \le i < j < k \le n$。
• $a_i,a_j,a_k$ 两两不同。
• $a_i < a_j > a_k$ 或者 $a_i>a_j<a_k$。

$n \le 10^6$，$a_i \le 10^9$。

我的思路：类似权值树状数组求逆序对，但是还需要对于逆序对数量再求一个逆序对。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1000005
#define lowbit(x) (x & -x)
 
int n, tot, ans;
int a[MAXN], b[MAXN], cnt[MAXN];
vector<int> p[MAXN];
 
struct BIT{
    int c[MAXN];
    void add(int x, int k){
        while (x <= n){
            c[x] += k;
            x += lowbit(x);
        }
    }
     
    int query(int x){
        int res(0);
        while (x){
            res += c[x];
            x -= lowbit(x);
        }
        return res;
    }
}t1, t2, t3, t4;
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     
    cin >> n;
    if (n <= 2){
        cout << 0;
        return 0;
    }
     
    for (int i(1); i<=n; ++i){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b+1, b+n+1);
    tot = unique(b+1, b+n+1)-b-1;
    for (int i(1); i<=n; ++i){
        a[i] = lower_bound(b+1, b+tot+1, a[i])-b;
        p[a[i]].push_back(i);
    }
    for (int i(1); i<=tot; ++i){
        for (int j(1); j<p[i].size(); ++j) ans -= (p[i][j]-p[i][j-1]-1)*(p[i].size()-1);
    }
     
    for (int i(1); i<=n; ++i){
        ans += t2.query(a[i]-1);
        t2.add(a[i], t1.query(n)-t1.query(a[i]));
        t1.add(a[i], 1);
    }
    for (int i(1); i<=n; ++i){
        ans += t4.query(n)-t4.query(a[i]);
        t4.add(a[i], t3.query(a[i]-1));
        t3.add(a[i], 1);
    }
     
    cout << ans;
 
    return 0;
}

但是 WA 了。