形式化题目

给定 $y_1,\dots,y_n$ 是 $1\sim n$ 的一个排列。对每个下标三元组 $1\leqslant i<j<k\leqslant n$：

• 若 $y_i>y_j$ 且 $y_j<y_k$，称 $(i,j,k)$ 构成 V 图腾（$j$ 是谷）；
• 若 $y_i<y_j$ 且 $y_j>y_k$，称 $(i,j,k)$ 构成 ∧ 图腾（$j$ 是峰）。

求 V 图腾与 ∧ 图腾的个数。

样例：$n=5$，$y=[1,5,3,2,4]$，答案为 3 4。

正解

思路

1. 朴素做法与瓶颈

最直接的做法是三层循环枚举 $(i,j,k)$，对每个三元组做两次比较，$O(n^3)$。 $n=200000$ 时约 $1.3\times10^{15}$ 个三元组，无论常数多小都跑不完。

稍微聪明一点：注意 V 的判定 $y_i>y_j,\ y_j<y_k$ 中没有任何一项同时涉及 $i$ 和 $k$。 换言之，一旦 $j$ 定下来，$i$ 的合法性与 $k$ 的合法性是两件互不相干的事， 可以只枚举 $j$ 与 $(i,k)$：对每个 $j$ 数出左边比它大的个数、右边比它大的个数，相乘再累加。 这样降到 $O(n^2)$，但 $4\times10^{10}$ 仍然不可行。

两种朴素做法的共同瓶颈是同一批元素被反复扫描：每个 $j$ 都要重新数一遍左边有多少个比它大的， 而 $j$ 从 $1$ 走到 $n$ 时，"已扫描集合"每次只是多了一个元素。

2. 固定中间点：$i$ 与 $k$ 的条件互相独立

这是整道题的枢纽。对固定的 $j$，定义四个集合

因为 $y$ 是排列、元素两两不同，每个 $i$ 恰好落在 $A^{>}_j$ 或 $A^{<}_j$ 之一，$k$ 同理。 $i<j<k$ 的次序已经由集合定义保证，两个条件又互不牵连，所以：

每个三元组的中间点唯一，所以按 $j$ 分类既不重也不漏。

3. 四个计数只需两个：互补量由下标总数给出

$A^{>}_j$ 与 $A^{<}_j$ 加起来正好是 $j$ 左边的全部元素，$B^{>}_j$ 与 $B^{<}_j$ 加起来是 $j$ 右边的全部元素。于是只要会算"更小的个数"就够了：

（上式用 $1$ 开始的下标；代码走 0 开始，左侧总数与右侧总数分别是 $j$ 和 $n-1-j$。 后文为对照代码统一用 0 基记号。）

4. 用权值树状数组把"数一遍"降到 $O(\log n)$

现在唯一要回答的问题变成：已经扫过的元素里，权值比 $y_j$ 小的有几个。 把元素从 $1$ 到 $n$ 依次插入，每次插入前先查一次前缀和：

• tree 是一棵权值树状数组，tree 上区间 $[1,v)$ 的和 = 已插入元素中权值 $<v$ 的个数；
• 查询 query(y_j-1) 得到的就是 $|A^{<}_j|$；
• 查询完再 add(y_j, 1)，把当前元素登记进去。

因为查的是"插入之前"的状态，统计到的自然只有 $j$ 左边的元素，不用额外排除自己。 又因为 $y$ 是 $1\sim n$ 的排列，权值范围恰好是 $1..n$，不需要离散化。 单次查询与插入各 $O(\log n)$，全程 $O(n\log n)$。

5. 反向扫描复用同一个函数

右侧计数 $|B^{<}_j|$ 不用另写一份镜像代码：把序列反转后，“原位置 $j$ 右侧比它小” 就变成"反转序列中对应位置左侧比它小"。所以

1right = prefix_less(a[::-1], n)[::-1]   # 得到的结果整体倒序，下标重新对齐

同一份 prefix_less 被调用两次，一次正序、一次倒序，四个计数就齐了。

6. 样例推演

把 $n=5$、$y=[1,5,3,2,4]$ 逐位置拆开，表中的数字都用 0 基下标下的互补公式 $L^{>}=j-L^{<}$、$R^{>}=(n-1-j)-R^{<}$ 算得：

读法：$L^{<},R^{<}$ 是代码里真正求出的两个数组（左侧 / 右侧比它小的个数）， $L^{>},R^{>}$ 由同一行的下标总数减出来。以 $j=1$（$y_j=5$）为例， 左边只有 $y_0=1$ 比它小，右边 $3,2,4$ 全比它小，所以 ∧ 贡献 $1\times3=3$、V 贡献 $0$—— 这与"最大值只能当峰"的直觉一致。把所有行分别相加，得到 3 4。

代码

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/**
 * 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-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 权值树状数组扫两遍，统计「V」与「∧」两种三元组个数。
#include <cstdio>

typedef long long ll;

const ll MAXN = 200005;

ll n;
ll a[MAXN];      // 原始排列（值域 1..n）
ll rev[MAXN];    // a 的反转
ll tree[MAXN];   // 权值树状数组
ll lessL[MAXN];  // lessL[j]：j 左侧比 a[j] 小的个数
ll lessR[MAXN];  // lessR[j]：j 右侧比 a[j] 小的个数

// less[j] = seq[j] 前面（已扫过的部分）比它小的元素个数
void prefix_less(ll* seq, ll* out) {
    for (ll i = 0; i <= n; i++) {
        tree[i] = 0;
    }
    for (ll j = 0; j < n; j++) {
        ll value = seq[j];
        ll i = value - 1;
        ll s = 0;
        while (i) { // 前缀和 [1, value-1]
            s += tree[i];
            i -= i & -i;
        }
        out[j] = s;
        i = value; // 把 value 插进树状数组
        while (i <= n) {
            tree[i]++;
            i += i & -i;
        }
    }
}

ll rawR[MAXN];

int main() {
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    for (ll i = 0; i < n; i++) {
        rev[i] = a[n - 1 - i];
    }

    prefix_less(a, lessL);
    prefix_less(rev, rawR); // 对反转序列做同样的扫描，再翻回来
    for (ll i = 0; i < n; i++) {
        lessR[i] = rawR[n - 1 - i];
    }

    // 左侧更大的个数 = 左侧总数 j 减去左侧更小的；右侧总数是 n-1-j
    ll vCount = 0, hatCount = 0;
    for (ll j = 0; j < n; j++) {
        vCount += (j - lessL[j]) * (n - 1 - j - lessR[j]); // V：左大右大
        hatCount += lessL[j] * lessR[j];                   // ∧：左小右小
    }
    printf("%lld %lld\n", vCount, hatCount);
    return 0;
}

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#!/usr/bin/env python3
# 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-10-01 17:40
# update_at: 2026-10-01 17:43

import sys


def prefix_less(seq: list[int], n: int) -> list[int]:
    """权值树状数组扫一遍：less[j] = seq[j] 前面（已扫过的部分）比它小的元素个数。

    传入 seq[::-1] 再翻转结果，就得到每个位置右侧比它小的个数，
    所以 V 与 ∧ 的四个计数只需要这一个函数。
    """
    tree = [0] * (n + 1)
    less: list[int] = []
    for value in seq:
        i = value - 1
        s = 0
        while i:                       # 前缀和 [1, value-1]：比 value 小的个数
            s += tree[i]
            i -= i & -i
        less.append(s)
        i = value                      # 把 value 插进树状数组
        while i <= n:
            tree[i] += 1
            i += i & -i
    return less


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]

    left = prefix_less(a, n)                 # left[j]：j 左侧比 a[j] 小的个数
    right = prefix_less(a[::-1], n)[::-1]    # right[j]：j 右侧比 a[j] 小的个数

    # 左侧更大的个数 = 左侧总数 j 减去左侧更小的；右侧同理，右侧总数是 n-1-j。
    # 与右侧部分做笛卡尔积，就分别是 V（左大右大）和 ∧（左小右小）的数目。
    print(sum((j - l) * (n - 1 - j - r) for j, (l, r) in enumerate(zip(left, right))),
          sum(l * r for l, r in zip(left, right)))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(n\log n)$。树状数组被调用两次，每次 $n$ 轮查询 + $n$ 轮插入， 每轮 $O(\log n)$；末尾两个求和是 $O(n)$。与标准 C++ 正解（树状数组 / 线段树 / 归并）同阶。
• 空间复杂度：$O(n)$，来自树状数组、两个计数数组和反转序列的拷贝。

实测（Apple Silicon / CPython 3.14）：最大一组 $n=200000$ 用时 0.43 s、峰值内存 55.6 MB， 低于 1000 ms / 128 MB 的限制；$n=190000$ 一组为 0.30 s / 52.2 MB。

总结

• 看到"数三元组"先问一句：这些条件能不能按中间点拆开。本题 V、∧ 的两个不等式分别只涉及 $(i,j)$ 与 $(j,k)$，拆开后左右两侧独立，计数就从"枚举配对"变成"两个数相乘"。
• 拆完只需求"左边有多少个比它小"。这类动态前缀和（集合单调增长、反复问前缀） 是树状数组的标准信号；权值是 $1\sim n$ 的排列则省掉了离散化。
• 互补量用下标总数减：四个计数只要求两个，少写一半代码也少一半出错机会。
• 反转序列复用函数：右侧计数就是反转后的左侧计数，位置上的对应关系靠 [::-1] 还原。 这比写一个 suffix_less 更短，也不会出现两边边界处理不一致的 bug。
• 查询必须在插入之前做，这样统计范围天然是"已扫过的元素"，不用再减掉自己。

图示解析

下面这张图串起从朴素枚举到 $O(n\log n)$ 的完整主线，重点是"条件按中间点分裂"这一步：

flowchart TD
    A["枚举全部三元组 i,j,k：O(n^3)，爆掉"] --> B["固定中间点 j<br/>两个不等式分别只涉及 (i,j) 与 (j,k)"]
    B --> C["V：左边更大的个数 x 右边更大的个数"]
    B --> D["∧：左边更小的个数 x 右边更小的个数"]
    C --> E["只需左侧更小的个数 L 与右侧更小的个数 R<br/>其余两个由下标总数互补算出"]
    D --> E
    E --> F["权值树状数组正序扫描<br/>L[j] = 左侧比 a[j] 小的个数"]
    E --> G["反转序列再调用同一函数<br/>R[j] = 右侧比 a[j] 小的个数"]
    F --> H["V = sum (j - L[j]) * (n-1-j - R[j])"]
    G --> H
    F --> I["∧ = sum L[j] * R[j]"]
    G --> I

读图时抓两条分叉：第一条说明为什么可以相乘（$i$ 与 $k$ 的条件互不相干， 中间点是唯一的分类依据）；第二条说明为什么只求两个数组就够（左侧与右侧的大小关系 各自互补，总数由下标给出），以及右侧数组为什么不必单独实现（反转序列后同一个函数即可）。

再看一眼树状数组在这道题里到底"数"了什么。以样例前三个元素 $1,5,3$ 为例：

这张表展示了"查询在插入之前"的含义：处理 $y_2=3$ 时，集合里还只有 $y_0,y_1$， 所以数出来的 1 就精确等于 $|A^{<}_2|$；如果先插入再查询，就会把 $3$ 自己算进去。