思路与算法

所有首项为三者最小的三元组，后两项只有递增123或下降132两种。先由右向左用Fenwick求每个位置右侧更大元素数g，贡献C(g,2)。再由左向右，用第一棵树求已见小于当前值的数目，作为第二棵树的权；第二棵树的小值前缀和给出以当前点为末项的123数量。二者相减。

正确性说明

排列中无相等值，首项最小的每组三下标恰归入123或132且互斥。右侧任选两更大值统计前者总集合；双Fenwick依次累加长度1和2的上升子序列，精确计数123。差值因此正是题目132。

复杂度

三棵Fenwick初始化O(N)，每点常数次单点增加/前缀和O(logN)，总O(NlogN)时间、O(N)空间。三元组总量用64位。

易错点

题面方便编程约定输入为1..N排列，因此无需压缩。严格小于查询a-1；右侧更大应减去不大于当前值的数量。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct BIT {
    int n;
    vector<long long> a;
    BIT(int n) : n(n), a(n + 1) {
    }
    void add(int i, long long v) {
        for (; i <= n; i += i & -i)
            a[i] += v;
    }
    long long sum(int i) {
        long long s = 0;
        for (; i; i -= i & -i)
            s += a[i];
        return s;
    }
};
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;
    BIT b(n), c(n);
    long long inc = 0, firstmin = 0;
    for (int i = 0; i < n; i++) {
        long long small = b.sum(a[i] - 1);
        inc += c.sum(a[i] - 1);
        c.add(a[i], small);
        b.add(a[i], 1);
    }
    BIT r(n);
    for (int i = n - 1; i >= 0; i--) {
        long long greater = n - 1 - i - r.sum(a[i]);
        firstmin += greater * (greater - 1) / 2;
        r.add(a[i], 1);
    }
    cout << firstmin - inc << '\n';
}