三元上升子序列

题意

统计 i < j < k 且 a[i] < a[j] < a[k] 的三元组数量。

思路

固定中间位置 j。左侧比 a[j] 小的个数乘右侧比它大的个数，就是以 j 为中间点的方案数。离散化后，正向 Fenwick 查询严格更小的排名，反向 Fenwick 查询严格更大的排名，最后求乘积之和。

Python 知识

sorted(set(values)) 加字典推导式完成离散化。
反向扫描时用 seen - prefix(rank) 处理严格大于，避免重复值被计入。
zip(left_count, right_count) 直接组合两个计数列表。

代码

python

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
40import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n, values = data[0], data[1:]
rank = {value: index for index, value in enumerate(sorted(set(values)), 1)}
size = len(rank)


def add(tree, index):
    while index <= size:
        tree[index] += 1
        index += index & -index


def query(tree, index):
    result = 0
    while index:
        result += tree[index]
        index -= index & -index
    return result


left_count = []
tree = [0] * (size + 1)
for value in values:
    position = rank[value]
    left_count.append(query(tree, position - 1))
    add(tree, position)

right_count = [0] * n
tree = [0] * (size + 1)
seen = 0
for index in range(n - 1, -1, -1):
    position = rank[values[index]]
    right_count[index] = seen - query(tree, position)
    add(tree, position)
    seen += 1

print(sum(left * right for left, right in zip(left_count, right_count)))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-16 23:46
 * update_at: 2026-07-16 23:46
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

离散化 O(n log n)，两次 Fenwick 扫描 O(n log n)，空间 O(n)。

总结

三元组计数的关键是固定中间点，把三维条件拆成两个一维前缀统计。

目录

题意

思路

Python 知识

代码

复杂度

总结