三元上升子序列

形式化题目

给定长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$ ，统计满足

i < j < k \quad \text{且} \quad a_i < a_j < a_k

的下标三元组 $(i, j, k)$ 的数量。值比较要求严格小于，相等的元素不能组成 thair。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:09
 * update_at: 2026-08-12 22:09
 */
// brute.cpp：小数据暴力解，O(n^3) 三重循环直接枚举所有 i<j<k，
// 检查 a[i] < a[j] < a[k] 是否成立，天然符合题意，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int n;
int a[MAXN]; // 输入序列

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 三重循环直接枚举三元组 (i, j, k)，满足 i<j<k 且值严格递增。
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (a[i] < a[j] && a[j] < a[k]) {
                    ans++;
                }
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

brute.cpp 三重循环枚举所有下标三元组并逐一检查值的大小关系，逻辑与题意一一对应，但 $O(n^3)$ 在 $n = 3 \times 10^4$ 时无法通过。

关键观察是固定中间点拆分：对任意固定位置 $j$ ，以 $j$ 为中间点的合法三元组，左侧随便取一个"值小于 $a_j$ "的位置 $i$ ，右侧随便取一个"值大于 $a_j$ "的位置 $k$ ，下标顺序与值顺序都会自动满足。所以

\text{以 } j \text{ 为中间点的方案数} = \#\{i<j \mid a_i < a_j\} \times \#\{k>j \mid a_k > a_j\}

这里体现了题目的双重本质。一是二维偏序：条件 $i<j \wedge a_i<a_j$ 是位置、值两个维度上的偏序关系，每个合法三元组就是一条"链长为 3"的偏序链；固定中间点 $j$ 后，左右两侧各退化为一个独立的二维偏序计数（左小、右大）。二是贡献计数：左右两个偏序统计互不干扰，用乘法原理合并，且每个三元组被唯一归到其中间点，累加不重不漏。正是这种拆分让复杂度从三维套叠降到 $O(n \log n)$ ，无需 CDQ 分治。

于是问题变成对每个位置求"左边比它小的个数"和"右边比它大的个数"，二者相乘再求和。为了高效统计这两个量，先把值离散化成排名（相同值排名相同），再用树状数组做两次扫描：

正向扫描：从左到右，树状数组里恰好存着左侧已出现位置的排名。left[i] = 前缀和(rk[i]-1) 数出严格小于 $a_i$ 的个数，然后插入 $a_i$ 的排名。
反向扫描：从右到左，用 seen 记录右侧已出现元素总数，right[i] = seen - 前缀和(rk[i]) 把排名 $\leqslant rk[i]$ 的排除掉，剩下的就是严格大于 $a_i$ 的个数。

两张统计都严格排除相等值：正向用 rk[i]-1，反向用 seen - prefix_sum(rk[i])，这是本题最容易错的地方。

下面这张表以样例 2（1 2 2 3 4，答案 7）展示每个中间位置的拆分结果：

位置 $j$	$a_j$	左侧小于 $a_j$ 的个数	右侧大于 $a_j$ 的个数	乘积（以 $j$ 为中间点的方案数）
1	1	0	4	0
2	2	1	2	2
3	2	1	2	2
4	3	3	1	3
5	4	4	0	0

观察要点：位置 2 与位置 3 的值相同（都是 2），但作为两个不同的中间点各算一份方案；每个位置的左小/右大都排除了与自身相等的值；总和 $0+2+2+3+0=7$ 与样例答案一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:09
 * update_at: 2026-08-12 22:09
 */
// P1637 三元上升子序列
// 离散化 + 两个树状数组正反两遍扫描：
// 正向统计每个位置左边比它小的个数，反向统计右边比它大的个数，
// 固定中间点 j，以 j 为中间数的三元组数 = 左小个数 * 右大个数。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30005;

int n;
int a[MAXN];       // 原始输入序列
int rk[MAXN];      // rk[i]：a[i] 离散化后的排名（1..m，值越小排名越小）
int sorted_vals[MAXN]; // 排序去重后的值，用于二分求排名
int m;             // 不同值的个数（树状数组大小）

long long left_cnt[MAXN];  // left_cnt[i]：i 左边严格小于 a[i] 的个数
long long right_cnt[MAXN]; // right_cnt[i]：i 右边严格大于 a[i] 的个数

// 树状数组：单点加、前缀和，下标从 1 开始。
// 仿照 rbook 模板 fenwick（树状数组单点加与前缀和模板）。
template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    static int lowbit(int x) {
        return x & -x;
    }

    // 给位置 pos 增加 value。
    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    // 求 [1, pos] 的前缀和。
    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }
};

// 离散化：把 a[1..n] 的值映射成 1..m 的排名，相同值排名相同。
void discretize() {
    for (int i = 1; i <= n; i++) {
        sorted_vals[i] = a[i];
    }
    sort(sorted_vals + 1, sorted_vals + n + 1);
    m = unique(sorted_vals + 1, sorted_vals + n + 1) - (sorted_vals + 1);
    for (int i = 1; i <= n; i++) {
        rk[i] = lower_bound(sorted_vals + 1, sorted_vals + m + 1, a[i]) - sorted_vals;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    discretize();

    // 正向扫描：树状数组记录已经出现过（在 i 左边）的各排名个数。
    // 严格小于 a[i] 的数，排名小于 rk[i]，个数就是前缀和 rk[i] - 1。
    Fenwick<int> bit(m);
    for (int i = 1; i <= n; i++) {
        left_cnt[i] = bit.prefix_sum(rk[i] - 1);
        bit.add(rk[i], 1);
    }

    // 反向扫描：树状数组记录 i 右边已经出现过的各排名个数。
    // 已扫描的个数 seen 减去"排名 <= rk[i] 的个数"就是严格大于 a[i] 的个数。
    Fenwick<int> bit2(m);
    int seen = 0;
    for (int i = n; i >= 1; i--) {
        right_cnt[i] = seen - bit2.prefix_sum(rk[i]);
        bit2.add(rk[i], 1);
        seen++;
    }

    // 以位置 i 为三元组中间数的方案数 = 左小个数 * 右大个数。
    // 答案最大接近 C(30000,3)，必须用 long long。
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += left_cnt[i] * right_cnt[i];
    }
    cout << ans << '\n';

    return 0;
}

复杂度

时间：离散化 $O(n \log n)$ ，两次树状数组扫描各 $O(n \log n)$ ，总 $O(n \log n)$ 。
空间：各数组与两个树状数组共 $O(n)$ 。

总结

三元组计数题的本质是二维偏序 + 贡献计数：i<j 且 a[i]<a[j] 就是位置、值两维上的偏序，合法的三元组是一条链长为 3 的偏序链。标准套路是固定中间点，把三维条件拆成"左边满足什么、右边满足什么"两个独立的二维偏序统计，再用贡献计数（每个三元组被唯一归到中间点）乘积累加。本题的两侧统计"严格小于/大于"用树状数组的两遍扫描完成：正向查询排名小于当前值的个数，反向用总数减去排名不超过当前值的个数。离散化 + 树状数组是这类偏序计数题的通用组合，逆序对、二维偏序计数都可以用同样的模型迁移。rbook 的《树状数组：单点修改与区间查询》讲解了本解所用 Fenwick 模板（fenwick，树状数组单点加与前缀和）的块结构与复杂度来源。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19暴力（brute.cpp）
  三重循环枚举所有 i<j<k，逐个检查 a[i]<a[j]<a[k]
        |
        | 瓶颈：O(n^3)，n=30000 时约 2.7e13 次判断
        v
关键观察：固定中间点 j
  以 j 为中间点的方案数 = 左侧比 a[j] 小的个数 × 右侧比 a[j] 大的个数
        |
        v
离散化：值映射成 1..m 的排名（相同值排名相同），树状数组规模 O(m)
        |
        v
两次树状数组扫描（main.cpp）
  正向：左边比 a[i] 小的个数  = prefix_sum(rk[i]-1)，再插入 rk[i]
  反向：右边比 a[i] 大的个数  = seen - prefix_sum(rk[i])，再插入 rk[i]
        |
        v
答案 = sum(左小 × 右大)，long long 累加
复杂度 O(n log n)，空间 O(n)

图中三条主线分别对应"暴力慢在哪"“观察到什么结构”“正式解如何利用该结构”。树状数组在正向扫描中扮演"左侧已见元素的排名计数"，在反向扫描中扮演"右侧已见元素的排名计数"；两个前缀和公式的差别（rk-1 对 seen - rk）正对应"严格小于"与"严格大于"两侧的不对称性。

目录

形式化题目

思路

代码

复杂度

总结

图示解析