统计排列中 132 型三元组:一遍正序扫描,树状数组给出左侧更小个数,借“元素互不相同”反推出右侧更大个数,边扫边累加 C(last,2)-pre·last。
OJ: roj
题目 ID: 1743
难度:提高
标签:树状数组计数排列python
创建: 2026-10-07 21:00
更新: 2026-10-07 21:00
形式化题目
给定一个长度为
也就是:按位置
正解
思路
最直接的做法是枚举
先看一个"错位"的现象:如果固定 last 个,任取两个就能凑出一个
:大小顺序是 (递增三元组),不符合; :大小顺序是 ,正是我们要数的。
所以只要能从
两个求和都只是标量累加,可以合并进同一遍循环,每个位置算一次。这就是经典的 132 计数恒等式。
现在只剩"怎么求
关键在于
这一步把两次树状数组扫描压成了一次。代入恒等式,每个位置
累加起来就是答案。若输入是
用题面样例
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 版:
#!/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++ 版(同一算法):
/**
* 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;
}复杂度
时间
总结
本题是"树状数组 + 组合恒等式"的入门应用。核心有三点:一是把计数摊到每个元素上,用"以 long long(Python 整数天然无上限)。
注意本题素材源中的 data/ 由随题的 data.py 用固定种子自行生成(并非官方数据),题面也是按网络题面重建的,因此出题意图与官方原题可能存在偏差;上面的解法按题面定义严格推导,已用暴力枚举对拍验证:main.cpp 与 main.py 均与暴力结果完全一致。