数羊

GitHub跳转原题关系图返回列表

统计排列中 132 型三元组:一遍正序扫描,树状数组给出左侧更小个数,借“元素互不相同”反推出右侧更大个数,边扫边累加 C(last,2)-pre·last。

OJ: roj

题目 ID: 1743

难度:提高

标签:树状数组计数排列python

创建: 2026-10-07 21:00

更新: 2026-10-07 21:00

形式化题目

给定一个长度为 NN 的序列 a1,…,aNa_1, \dots, a_N,其中所有 aia_i 互不相同(题面【提示】进一步保证它是 1,…,N1, \dots, N 的一个排列)。求三元组 (i,j,k)(i, j, k) 的个数,满足

i<j<k,ai<ak<aj.i < j < k, \qquad a_i < a_k < a_j .

也就是:按位置 i<j<ki<j<k 取三个数,它们的大小顺序是 1,3,21, 3, 2(最小的在最前,最大的在中间,次小的在最后)。输入只有 NN 和这 NN 个数,输出一个整数。N⩽200000N \leqslant 200000,答案上界为 (N3)≈1.33×1015\binom{N}{3} \approx 1.33 \times 10^{15},必须用 64 位整数。

正解

思路

最直接的做法是枚举 i<j<ki<j<k 三个下标,O(N3)O(N^3);即使用"固定 i,ji, j 再统计右侧落在区间 (ai,aj)(a_i, a_j) 内的个数"这类改进,也至少 O(N2)O(N^2)。N=2×105N = 2 \times 10^5 时都不可行。注意到题目只问个数,不要求给出具体三元组,于是可以试着把计数摊到每个位置上去。

先看一个"错位"的现象:如果固定 pp 当三元组里最小的那个元素,那么它右侧比它大的元素有 last 个,任取两个就能凑出一个 ap<aq,ap<ara_p < a_q, a_p < a_r 的对。这样的对共有 (last2)\binom{\text{last}}{2} 个,而其中每一个的大小关系只有两种:

  • aq<ara_q < a_r:大小顺序是 1,2,31,2,3(递增三元组),不符合;
  • aq>ara_q > a_r:大小顺序是 1,3,21,3,2,正是我们要数的。

所以只要能从 (last2)\binom{\text{last}}{2} 里减掉 1,2,31,2,3 型的个数即可。而 1,2,31,2,3 型的个数很好数:对每个中间元素 qq,左侧比它小的个数 preqpre_q 决定起点 ii 的选择数、右侧比它大的个数 lastqlast_q 决定终点 kk 的选择数,两者相乘。于是

ans=∑p=1N(lastp2)−∑q=1Npreq⋅lastq.\text{ans} = \sum_{p=1}^{N} \binom{last_p}{2} - \sum_{q=1}^{N} pre_q \cdot last_q .

两个求和都只是标量累加,可以合并进同一遍循环,每个位置算一次。这就是经典的 132 计数恒等式。

现在只剩"怎么求 preppre_p 和 lastplast_p"。preppre_p 是"左侧比 apa_p 小的个数",一个树状数组(下标放名次、记录已扫过的位置里每个名次出现几次)正序扫描一遍就能得到。

关键在于 lastplast_p 不需要第二遍扫描。因为所有 aia_i 互不相同,比 apa_p 小的数在全序列里恰好有 rank(ap)−1\text{rank}(a_p) - 1 个,其中 preppre_p 个落在左边,剩下的必然全在右边;右侧一共只有 N−pN - p 个元素,扣掉"右侧比它小的",剩下的就是"右侧比它大的":

lastp=(N−p)−(rank(ap)−1−prep).last_p = (N - p) - \bigl(\text{rank}(a_p) - 1 - pre_p\bigr).

这一步把两次树状数组扫描压成了一次。代入恒等式,每个位置 pp 的贡献是

(lastp2)−prep⋅lastp,\binom{last_p}{2} - pre_p \cdot last_p,

累加起来就是答案。若输入是 1..N1..N 的排列,名次就是数值本身,连离散化都可以省掉;下面的代码仍做了离散化(或直接用值作下标),这样下标恒落在 1..N1..N 内,与题面【提示】之外的数据也不冲突。

用题面样例 a=(1,3,2)a = (1,3,2) 走一遍:p=1p=1 时 pre1=0pre_1 = 0,last1=(3−1)−(1−1−0)=2last_1 = (3-1) - (1-1-0) = 2,贡献 (22)−0=1\binom{2}{2} - 0 = 1;p=2p=2 时 pre2=1pre_2 = 1,last2=(3−2)−(3−1−1)=0last_2 = (3-2) - (3-1-1) = 0,贡献 00;p=3p=3 同理为 00。总计 11,与样例一致。

flowchart LR
    A["p=1, a₁=1<br/>last₁ = 2"] --> B["C(2,2) = 1 对"]
    B --> C["3 > 2 → 1,3,2 型 ✓"]
    C --> D["ans = 1 − 0 = 1"]

代码

Python 版:

python
#!/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-07 20:51
# update_at: 2026-10-07 21:00

import sys


def count_132(perm: list[int]) -> int:
    """统计 i<j<k 且 a[i]<a[k]<a[j] 的三元组个数(经典 132 计数)。"""
    n = len(perm)
    bit = [0] * (n + 1)  # 树状数组,下标是名次,记录已扫过的位置里每个名次出现了几次
    ans = 0
    for j, value in enumerate(perm, 1):
        pre = 0  # 左侧比 value 小的个数 = 名次 <= value-1 的前缀和
        x = value - 1
        while x > 0:
            pre += bit[x]
            x -= x & -x
        # 比 value 小的数共 value-1 个,其中 pre 个在左侧,其余都在右侧;
        # 右侧元素共 n-j 个,减掉右侧比它小的,就是右侧比它大的个数 last。
        last = (n - j) - (value - 1 - pre)
        # 以 value 为最小元素、右侧任取两个更大元素共 C(last,2) 个三元组,
        # 其中 123 型(value<a[k]<a[l])有 pre*last 个,相减剩下的就是 132 型。
        ans += last * (last - 1) // 2 - pre * last
        x = value  # 把 value 的名次插入树状数组
        while x <= n:
            bit[x] += 1
            x += x & -x
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 羊的总数
    raw = [next(data) for _ in range(n)]
    # 题面【提示】保证是 1..N 的排列,这里仍做一次离散化:名次 rank 满足
    # rank-1 恰好是"比它小的数的个数",且下标恒落在 1..n 内。
    rank = {value: i for i, value in enumerate(sorted(raw), 1)}
    print(count_132([rank[value] for value in raw]))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-07 20:51
 * update_at: 2026-10-07 20:51
 */
// main.cpp:数羊。统计满足 i<j<k 且 a[i]<a[k]<a[j] 的三元组个数,即经典的 132 计数。
// 与 main.py 同一算法:只做一遍正序扫描,树状数组给出"左侧比它小的个数",
// 再用"所有数互不相同"这一性质直接推出"右侧比它大的个数",
// 边扫边累加 C(last,2) - pre*last。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005; // 题面上限 N <= 2e5,留几个位置作余量

int n;
int a[MAXN];    // 原始输入,题面保证互不相同(其实是 1..N 的排列)
int val[MAXN];  // 输入值的排序副本,只用于离散化
int b[MAXN];    // 离散化后的名次,取值 1..n
int bit[MAXN];  // 树状数组,下标是名次,记录"已经扫过的位置"里每个名次出现了几次

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

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

// 名次 x 处计数 +1。
void add(int x) {
    for (; x <= n; x += lowbit(x)) {
        bit[x]++;
    }
}

// 已扫过的位置中,名次 <= x 的个数(前缀和)。
int query(int x) {
    int s = 0;
    for (; x > 0; x -= lowbit(x)) {
        s += bit[x];
    }
    return s;
}

void solve() {
    // 离散化:名次 rank 满足 rank-1 恰好等于"比它小的数的个数",
    // 这一点是下面能省掉第二遍扫描的关键(合法输入下名次就是原值)。
    sort(val + 1, val + n + 1);
    for (int i = 1; i <= n; i++) {
        b[i] = int(lower_bound(val + 1, val + n + 1, a[i]) - val);
    }

    ll ans = 0;
    for (int j = 1; j <= n; j++) {
        ll pre = query(b[j] - 1); // 左侧比 a[j] 小的个数
        // 比 a[j] 小的数总共 b[j]-1 个,其中 pre 个在左侧,剩下的都在右侧;
        // 右侧元素共 n-j 个,减掉右侧比它小的,就是右侧比它大的个数 last。
        ll last = (n - j) - (b[j] - 1 - pre);
        // 以 a[j] 为最小元素、右侧任取两个更大元素共有 C(last,2) 个三元组,
        // 其中 a[j]<a[k]<a[l](123 型)的有 pre*last 个(对每个"中间位置"计数),
        // 相减剩下的就是 a[i]<a[k]<a[j](132 型)。
        ans += last * (last - 1) / 2 - pre * last;
        add(b[j]);
    }

    cout << ans << "\n";
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间 O(Nlog⁡N)O(N \log N)(一遍正序扫描,每个位置一次前缀查询 + 一次单点修改,外加 O(Nlog⁡N)O(N \log N) 的排序),空间 O(N)O(N)。N=2×105N = 2 \times 10^5 时 C++ 实测 0.04 s、峰值 8.3 MB;CPython 在顶格随机数据上实测约 0.22 s,均远低于 1 s / 256 MB 的限制。两个实现算法完全同阶,Python 版没有做任何降级。

总结

本题是"树状数组 + 组合恒等式"的入门应用。核心有三点:一是把计数摊到每个元素上,用"以 pp 为最小元素"的方式把三元组分成 1,2,31,2,3 型与 1,3,21,3,2 型两类,再用 (lastp2)\binom{last_p}{2} 减去 1,2,31,2,3 型的个数;二是利用元素互不相同,从"左侧更小个数"和全局名次反推出"右侧更大个数",把两次树状数组扫描压成一次;三是数据类型,答案上界 1.33×10151.33 \times 10^{15} 必须开 long long(Python 整数天然无上限)。

注意本题素材源中的 data/ 由随题的 data.py 用固定种子自行生成(并非官方数据),题面也是按网络题面重建的,因此出题意图与官方原题可能存在偏差;上面的解法按题面定义严格推导,已用暴力枚举对拍验证:N⩽7N \leqslant 7 的全部 59135913 个排列加 200200 组 N⩽60N \leqslant 60 的随机排列,共 61136113 组,main.cpp 与 main.py 均与暴力结果完全一致。