官方题解｜独特三元组

题目解析

可以将问题转化为：“求满足 $A_i \lt A_j \lt A_k$ 的三元组 $(i, j, k)$ 的数量”。

对于满足题目原条件的三元组 $(i,j,k)$，有且仅有一个 $[A_i, A_j, A_k]$ 的排列 $P$，使得 $A_{P_1} \lt A_{P_2} \lt A_{P_3}$。
反之，对于有 $A_i\lt A_j\lt A_k$ 的三元组 $(i,j,k)$，有且仅有一个 $[i,j,k]$ 的排列 $P$，使得 $P_1 \lt P_2\lt P_3$。

考虑枚举 $j$，那么 $i$ 和 $k$ 可以独立选择。
满足条件的 $i$ 的数量是 $A$ 中数值小于 $A_j$ 的元素个数；
满足条件的 $k$ 的数量是 $A$ 中数值大于 $A_j$ 的元素个数。
因此，只要准备一个数组 cnt，令 cnt[x] 为 $A$ 中小于等于 $x$ 的数量，便可以很容易地计算出满足条件的 $i$ 和 $k$ 的数量。

AC代码

C++ AC代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5;

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;
    int cnt[N + 1]{};
    for (auto &x : a)
        cnt[x] += 1;
    std::partial_sum(cnt, cnt + N + 1, cnt);
    i64 res = 0;
    for (auto &x : a)
        res += 1LL * cnt[x - 1] * (n - cnt[x]);
    std::cout << res << '\n';
    return 0;
}

Python AC代码：

N = 2 * 10**5
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (N + 1)
for x in a:
    cnt[x] += 1
for i in range(1, N + 1):
    cnt[i] += cnt[i - 1]
print(sum(cnt[x - 1] * (n - cnt[x]) for x in a))

复杂度分析

统计所有数字出现的次数，使用前缀和处理 cnt 数组，最终枚举 $j$ 统计答案，时间复杂度为 $\mathrm{O}(N + \max{A})$。