题目描述
在含有 n 个整数的序列 a1,a2,…,an 中，三个数被称作 thair 当且仅当 i<j<k 且 a[i]<a[j]<a[k]。求一个序列中 thair 的个数。
什么是三元上升子序列？
三元上升子序列是指在数组中选取三个位置 i、j、k（满足 i < j < k），同时满足 a[i] < a[j] < a[k] 的三个数。这是一个经典的计数问题，属于「上升子序列」系列题型的基础。
解题核心思想
对于每个位置 j（作为中间元素），我们需要：
- 统计它左边比 a[j] 小的元素个数，记为 L[j]
- 统计它右边比 a[j] 大的元素个数，记为 R[j]
- 以 j 为中间元素的三元组数量就是 L[j] × R[j]
为什么要离散化？
由于数组元素可能很大（1 ≤ a[i] ≤ 10^5），但 n 只有 30000，我们需要将大范围的数值映射到紧凑的索引范围。这个过程叫做离散化。
步骤：
- 复制原数组到 b[ ]
- 对 b 排序并去重
- 通过二分查找将原数组元素映射到 1~m 的索引
树状数组（Fenwick Tree）
树状数组是一种高效的数据结构，用于单点更新+区间查询，时间复杂度为 O(log n)。
核心操作：
- add(x, c)：在位置 x 增加 c
- query(x)：查询前缀和 [1, x]
这两个操作完美满足我们的需求：统计左边比当前元素小的个数，以及右边比当前元素大的个数。
算法步骤
- 离散化：将原数组元素映射到 1~m 的索引
- 从左到右扫描：用树状数组统计每个位置左边比它小的元素个数 L[i]
- 从右到左扫描：用树状数组统计每个位置右边比它大的元素个数 R[i]
- 累加结果：ans = Σ(L[i] × R[i])
完整代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=30010;
typedef long long LL;
int n;
int a[N]; // 原序列
int b[N]; // 离散化数组
int tr[N]; // 树状数组
int L[N], R[N]; // 左小、右大的个数
int lowbit(int x){
return x & -x;
}
void add(int x, int c){
for(; x<=n; x+=lowbit(x))
tr[x] += c;
}
int query(int x){
int res = 0;
for(; x>0; x-=lowbit(x))
res += tr[x];
return res;
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
// 离散化
sort(b+1, b+1+n);
int m = 1;
for(int i=2; i<=n; i++)
if(b[i] != b[m]) b[++m] = b[i];
// 第一遍扫描：统计左边比它小的个数
for(int i=1; i<=n; i++){
int k = lower_bound(b+1, b+1+m, a[i]) - b;
L[i] = query(k-1);
add(k, 1);
}
// 清空树状数组
for(int i=1; i<=n; i++) tr[i] = 0;
// 第二遍扫描：统计右边比它大的个数
for(int i=n; i>=1; i--){
int k = lower_bound(b+1, b+1+m, a[i]) - b;
R[i] = query(m) - query(k);
add(k, 1);
}
// 计算结果
LL ans = 0;
for(int i=1; i<=n; i++)
ans += (LL)L[i] * R[i];
printf("%lld\n", ans);
return 0;
}
复杂度分析
- 时间复杂度：O(n log n)，主要来自树状数组的两次扫描
- 空间复杂度：O(n)，用于存储数组和树状数组
注意：结果需要使用 long long 存储，因为最大可能达到 C(30000, 3) ≈ 4.5 万亿！