企业官网建设流程全解析

1. 题目拆解与题意理解

1.1 蓝桥杯这道题到底在考什么

递增三元组（原题在蓝桥杯省赛中出现过）是一道非常典型的“数组计数 + 枚举优化”问题。我最初拿到这道题的时候，第一反应是“这不就是三重循环嘛”，但在比赛环境下写了暴力代码提交后，果断吃了一个超时警告。这道题在当年的省赛中属于中等偏易的位置，但它考察的点非常集中：你是否能在暴力思路的基础上，找到一种更聪明的计数方式。

题目大致是这样：给定三个整数数组 A、B、C，长度都是 n，需要统计一共有多少组下标 (i, j, k) 满足 A[i] < B[j] < C[k]。注意这里 i、j、k 都是从各自的数组里取的，三个数组长度相等，取值范围通常在 1 到 100000 左右。也就是说，数据规模直接决定了你能不能靠暴力莽过去。

先说结论：n ≤ 1000 的时候，三重循环（O(n³)）勉强能跑；但 n 到 10⁵ 量级时，三重循环直接原地爆炸，必须优化到 O(n log n) 甚至 O(n) 才能稳妥通过。这个题最妙的地方就在于——它不会直接告诉你“要二分”，而是让你自己从数据范围里悟出这个需求。

1.2 输入格式和输出格式的细节

题目输入一般是三行，前两个数是 n，然后依次给出 A、B、C 三个数组。输出一个整数，表示满足条件的三元组总数。有些版本的题面会把范围给定为 1 ≤ n ≤ 10⁵，数组元素绝对值可能较大，但也可能是非负整数。

输出值的规模往往超出直觉：假如 A、B、C 都是升序排列，且每个元素都恰好满足条件，那么三元组数量就是 n³。n = 10⁵ 时，n³ ~ 10¹⁵，这远超 int 范围。所以答案类型一定建议用 long long（C++）或 Python 的 int（它天然不溢出，但某些语言如 Java 必须用 long）。我当年写 C++ 时第一次用 int 存答案，样例全过，大数据直接 WA，后来一查才发现是溢出。

另外，题目中并没有说数组元素互不相同。所以重复值的处理也要考虑进去——统计的时候是严格小于和严格大于，遇到相等的情况要特别小心边界。

2. 暴力解法为什么不可行：从复杂度开始说起

2.1 三重循环的直观思路

既然题目问有多少个三元组满足 A[i] < B[j] < C[k]，最自然的方法就是枚举所有可能的三元组，逐一判断条件是否成立。伪代码非常简单：

long long ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (A[i] < B[j] && B[j] < C[k]) { ans++; } } } }

这段代码读起来非常清爽，逻辑上没毛病。但你看一眼复杂度就知道问题在哪里了：三重循环一共要执行 n³ 次比较，n = 10⁵ 时是 10¹⁵ 次操作。普通 CPU 一秒钟大概能跑 10⁸~10⁹ 次简单操作，也就是说这个暴力代码在最坏情况下要跑几十万秒，估计比赛结束了它还在跑。所以暴力思路只能作为验算小样例的工具，绝不能作为最终提交的代码。

2.2 从暴力中提炼规律：B[j] 是关键枢纽

当你开始思考优化时，会发现一个核心事实：满足条件的三元组是由三个数组分别取值构成的，而中间值 B[j] 是联系 A 和 C 的枢纽。只要确定了 B[j]，问题就拆成了两个独立的小问题：

• A 中有多少个元素严格小于 B[j]？
• C 中有多少个元素严格大于 B[j]？

这两个数量乘起来，就是以 B[j] 作为中间值的所有合法三元组数量。然后把所有 B[j] 对应的结果累加，就是答案。

为什么会想到这个角度？因为“小于”和“大于”本质上是对一个已排序序列做区间查询的问题，而排序和二分正是处理区间查询最经典的手段。n = 10⁵ 的数据规模要求 O(n log n) 或 O(n) 的算法，排序的复杂度是 O(n log n)，刚好能承受。

我最初自己推导到这里时，最大的收获是意识到：很多看似复杂的题目，核心就是找到一个“不变量”或“中心变量”，把大问题拆成小问题。这道题的 B[j] 就是这个中心变量。

3. 解法一：排序 + 二分查找

3.1 整体思路：固定 B，二分计数

具体操作分三步：

1. 对 A 和 C 分别升序排序。
2. 遍历数组 B 的每一个元素 b。
3. 在排好序的 A 中用二分查找找到最后一个小于 b 的位置，在排好序的 C 中用二分查找找到第一个大于 b 的位置，然后累乘累加。

关于“最后一个小于 b 的位置”：C++ 标准库中有 lower_bound 和 upper_bound，用起来非常顺手。lower_bound 返回第一个大于等于目标值的位置，而 upper_bound 返回第一个大于目标值的位置。如果我们想数数组中有多少个小于 b 的元素，就是 upper_bound(A.begin(), A.end(), b) 得到的下标。因为数组下标从 0 开始，这个下标的值本身就等于小于 b 的元素个数。

同理，想数数组中有多少个大于 b 的元素，可以用数组长度减去 upper_bound(C.begin(), C.end(), b) 得到的下标——注意 upper_bound 得到的是第一个大于 b 的位置，所以后面跟着的全部都是大于 b 的，个数就是 n - pos。

得到两个计数 cntA 和 cntC 之后，累加 cntA * cntC 就行了。

3.2 C++ 样板代码与易错点

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n), b(n), c(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; i++) cin >> c[i]; sort(a.begin(), a.end()); sort(c.begin(), c.end()); long long ans = 0; for (int j = 0; j < n; j++) { int cntA = upper_bound(a.begin(), a.end(), b[j]) - a.begin(); int cntC = c.end() - upper_bound(c.begin(), c.end(), b[j]); ans += (long long)cntA * cntC; } cout << ans << endl; return 0; }

这段代码看起来简短，但有几个坑我必须强调一下。第一个是排序顺序对下标的影响：虽然排序后数组不再是原来的顺序，但我们关心的只是“小于某个值的数量”“大于某个值的数量”，这些数量跟原始顺序无关。排序不会影响统计结果，这一点想通了就不会慌。第二个坑是 upper_bound 返回的是迭代器，减 begin 得到的是个数，这个个数本身就是 cntA。如果你用 lower_bound，则会把等于 b[j] 的元素也包含进来，导致统计结果偏大——严格小于这个条件意味着等于的情况必须排除。

第三个坑是 cntA * cntC 可能超出 int。两个 10⁵ 级别的数相乘是 10¹⁰，这时候必须转成 long long 再做乘法。你可以在乘法前加 (long long) 强转，也可以把 cntA 和 cntC 定义成 long long。养成习惯最好。

我实测这段代码在 n = 10⁵ 时运行时间几十毫秒，完全在时间限制内。二分的实现细节很容易模糊，但你要记住核心：二分的目标是在有序序列中找到边界，upper_bound 找的是严格大于的边界，lower_bound 找的是大于等于的边界。这两个边界相差的地方正好是等于目标值的元素区间。

3.3 Python 版本与语言差异

如果你用 Python 参加蓝桥杯，代码逻辑一致，只是用 bisect 模块替换 C++ 的 lower_bound/upper_bound。这里有个细节：Python 的 bisect_right 等价于 upper_bound，bisect_left 等价于 lower_bound。

import bisect n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) c = list(map(int, input().split())) a.sort() c.sort() ans = 0 for x in b: cntA = bisect.bisect_left(a, x) # 小于 x 的个数 cntC = n - bisect.bisect_right(c, x) # 大于 x 的个数 ans += cntA * cntC print(ans)

这里用 bisect_left(a, x) 而不是 bisect_right(a, x)，是因为我们要统计“严格小于”的个数。如果 A 中有元素等于 x，bisect_left 会把它排除在左侧，而 bisect_right 会把它包进去，结果就差了几个。C 数组那边要统计大于 x 的个数，用 bisect_right 得到第一个大于 x 的下标，用 n 减掉就是右边剩余元素个数。Python 的 int 是任意精度的，所以 ans 不会溢出，省心不少，但运行时要注意大输入量的读取速度，建议用 sys.stdin.buffer.read() 一次性读入，避免 input() 逐行读取带来的性能开销。

4. 解法二：前缀和计数法（桶思想）

4.1 从二分到桶的思维跃迁

二分法的时间复杂度是 O(n log n)，已经很优秀了。但你有没有想过，能不能做到 O(n)？答案是可以，但这需要引入一个前提：数组元素的值域是有限的。如果 A[i]、B[j]、C[k] 的取值范围在 1 到 maxV 之间，而且 maxV 不是特别离谱（比如 ≤ 1000000），我们完全可以用一个计数数组来做预处理，这就是前缀和计数法。

核心思想是这样的：先对 A 中的每个值出现的次数做统计，得到一个频次数组 freqA。然后对这个频次数组求前缀和，得到 preA[value]——表示 A 中小于等于 value 的元素个数。同理，对 C 也做同样的桶统计和前缀和，得到 preC[value]。这样一来，对于任意 B[j] 的值 b，我们需要的“A 中小于 b 的个数”直接就是 preA[b - 1]（前提是 b > 0），而“C 中大于 b 的个数”就是 n - preC[b]。两次 O(1) 查询搞定。

这就像你有一本按字母排序的词典，二分法每次翻一半找单词，而桶法相当于提前把所有单词的页码都记在一张超大表格里，你直接查表就行。代价是表格需要占用跟值域一样大的空间。

4.2 代码实现与值域上限的判断

假设值域范围是 1 ≤ value ≤ 100000，可以直接开大小为 maxV + 5 的数组。C++ 代码大概长这样：

#include <bits/stdc++.h> using namespace std; const int MAXV = 100000; int main() { int n; cin >> n; vector<int> a(n), b(n), c(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = 0; i < n; i++) cin >> c[i]; vector<int> cntA(MAXV + 5, 0), cntC(MAXV + 5, 0); for (int x : a) cntA[x]++; for (int x : c) cntC[x]++; vector<long long> preA(MAXV + 5, 0), preC(MAXV + 5, 0); for (int i = 1; i <= MAXV; i++) { preA[i] = preA[i - 1] + cntA[i]; preC[i] = preC[i - 1] + cntC[i]; } long long ans = 0; for (int x : b) { long long cntLessA = (x > 0) ? preA[x - 1] : 0; long long cntGreaterC = n - preC[x]; ans += cntLessA * cntGreaterC; } cout << ans << endl; return 0; }

这个代码比我上面写的二分版更高效，但前提是值域不能太大。如果数组元素是负数或者值域大到 10⁹，那就没法开这么长的数组，bucket 法直接失效。你需要在拿到题目时快速判断值域上限，通常题面会给出约束条件。如果没有给出，最稳妥的还是排序+二分，因为它对值域没有任何要求。

4.3 二分法和前缀和法的对比

我在实际练习中会刻意把两种解法都写一遍，因为这是很好的思维训练。总结对比一下：

你可能会想“前缀和法明明更快，为什么不总用它？”原因就是它太吃值域。如果值域是 10⁹，数组都开不了，强行离散化又回到了排序二分的老路。所以实际比赛中，我最先想到的永远是二分法，只有看到值域约束特别友好的时候才切换到桶法。

5. 常见错误与调试技巧实录

5.1 排序导致的“下标错位”问题

我刚开始刷这道题时，犯过一个很傻的错误：先把 A、B、C 三个数组都排序了，然后固定的是排序后的 B[j]。表面看起来没问题，但如果你做了任何基于原始下标（比如同时取 A[i] 和 B[j] 的下标去做某种映射）的操作，排序会直接破坏下标对应关系。这道题虽然不需要下标对应，但很多变种题需要。所以建议只排序 A 和 C，B 保持不变，这样语义清晰，也不容易引发后续踩坑。

5.2 二分边界：lower_bound 还是 upper_bound

这是一个我见过无数人踩过的坑。统计小于 x 的个数时要用 upper_bound（也就是 bisect_right），因为 upper_bound 返回的是“第一个大于 x 的位置”，这个位置之前的元素全部小于等于 x？不对——upper_bound 是严格大于 x 的第一个位置，所以之前元素是全部小于等于 x？这里要仔细想：upper_bound 找的是第一个大于 x 的元素，它之前的元素都 ≤ x，而由于“第一个大于”的定义，等于 x 的那些元素统统在它之前。所以用 upper_bound 得到的下标，含义是“小于等于 x 的个数”，而不是“小于 x 的个数”。等一下，我再仔细想一想。

实际上，C++ 标准库中 upper_bound 返回的是第一个“大于 value”的元素的迭代器，这意味着它之前的所有元素都不大于 value，也就是 ≤ value。所以它给出的下标等于“≤ value 的元素个数”。如果要统计“严格小于 value 的个数”，应该用 lower_bound——lower_bound 返回第一个“大于等于 value”的迭代器，它之前的元素都严格小于 value，因此下标值就是“< value 的个数”。

这里我要澄清一下：在刚才给出的二分代码中，我写的是upper_bound(a.begin(), a.end(), b[j]) - a.begin()来统计小于 b[j] 的个数。这个写法其实是错的。我还需要确认一下——不，等一下，upper_bound 返回第一个大于 value 的位置，所以它之前是 ≤ value，不是 < value。正确写法应该是 lower_bound。我上面给出的代码有误，需要修正。正确的应该是：

int cntA = lower_bound(a.begin(), a.end(), b[j]) - a.begin(); // < b[j] 的个数 int cntC = c.end() - upper_bound(c.begin(), c.end(), b[j]); // > b[j] 的个数

C 那边统计大于 b[j] 的个数，upper_bound 返回第一个大于 b[j] 的位置，所以从它到末尾全部是大于 b[j] 的，这个没问题。

我在实际写题时经常把这两个函数搞混，所以后来总结了一个记忆技巧：lower_bound 对应“大于等于”，upper_bound 对应“大于”。要找“小于 x 的个数”就用 lower_bound（因为它把等于 x 的挡在右边）；要找“大于 x 的个数”就用 upper_bound（因为它把等于 x 的挡在左边）。

5.3 大数溢出：ans 用 int 会挂

前文已经提过，但这里再展开说说。n = 10⁵ 时，即使是合法三元组的数量也可能达到 10¹⁵ 量级。int 最大约 21 亿，long long 最大约 9 × 10¹⁸。所以正确答案类型、乘法中间值都必须用 long long。Python 无所谓，Java 必须用 long。

我还遇到过一个更隐蔽的问题：有些同学 cntA 和 cntC 是 int，乘法时先按照 int 相乘，溢出之后才转 long long，结果已经不对了。正确做法是先把其中一个强转成 long long，再乘。C++ 中(long long)cntA * cntC就是安全的。

5.4 边界情况：数组为空或者 n = 1

严格来说这类竞赛题 n 至少是 1，但你还是要想清楚 n = 1 时的行为：如果 A[0] < B[0] < C[0] 成立，答案为 1，否则为 0。二分的边界在 n = 1 时依然正确。前缀和法要特别注意 x 为最小值时 preA[x - 1] 的下标越界问题。我的习惯是所有下标都从 1 开始计数，避免 x - 1 为负的情况，或者用条件判断处理。

6. 竞赛视角下的延伸思考

6.1 这道题背后的通用思维模式

递增三元组这个题目，本质上考察的是“枚举中间值，拆分独立子问题”。这种套路在很多题目里都能看到影子。比如有两个数组，统计满足某种偏序关系的配对数量；再比如三维偏序问题——如果扩展成 A[i] < B[j] < C[k] < D[l]，虽然维度增加了，但核心思想不变。你只需要固定两个中间值或者用 CDQ 分治等更高级的手段。

我刷题时发现，很多看似需要用复杂数据结构的题，实际上都可以用“排序 + 二分/双指针”解决。关键在于能不能识别出哪个变量是“枢纽变量”。递增三元组里，B[j] 就是枢纽，因为它同时参与两个不等关系的判断。识别出枢纽之后，问题就被拆成了两个独立且简单的一维统计问题。

6.2 时间复杂度的心里有数

比赛时你不能只写出能过的代码就完事，还要估算最坏情况的运行时间。O(n log n) 在 n = 10⁵ 时大约执行 1.7 × 10⁶ 次“比较+赋值”，加上常数之后通常几十毫秒。O(n²) 是 10¹⁰ 量级，铁定超时。O(n³) 更是想都不用想。所以拿到题先看数据范围，再决定算法，这个习惯比任何技巧都重要。

6.3 如果继续优化：双指针可否做到 O(n)

二分法已经是 O(n log n)。但如果你再仔细想想，A 和 C 都已经排序好了，而 B 如果也排序，那么随着 B[j] 增大，A 中小于它的个数一定单调不减，C 中大于它的个数一定单调不增。这就可以用双指针把总复杂度降到 O(n)。思路是：用两个指针 pa 和 pc 分别指向 A 和 C，然后遍历排序后的 B。每次 b 增大时，向后移动 pa 直到 A[pa] ≥ b，pa 就是小于 b 的个数；同时从后往前移动 pc（或者从前往后记录边界），得到大于 b 的个数。但这里要注意，B 需要排序，而排序本身是 O(n log n)。如果题目保证 B 已经有序，双指针就是 O(n)；否则整体还是 O(n log n)，但常数更小。

我在实际练习中，喜欢把二分版、前缀和版、双指针版都写出来对比运行时间。这不是浪费时间，而是能帮你理解不同优化路径的本质。到了正式比赛，你自然会选择一个最顺手的写法。

6.4 题目变形预警

递增三元组有很多变种，最常见的是把“严格小于”变成“小于等于”，这时二分边界要相应改成 lower_bound/upper_bound 的对应组合。还有一种是统计“非递减三元组”，条件变成 a[i] ≤ b[j] ≤ c[k]，处理方式类似，只是边界函数换一下。如果变成“和为定值的递增三元组”，那还要引入哈希表记录中间状态。总之你理解了核心套路，变种题无非是加一点维度或者改一下边界条件。

7. 实操心得与最后的建议

刷完这道题，我最大的体会是：写代码前一定要先在纸上把“枢纽变量”画出来。三重循环的直觉让你一下子陷入思维定式，但只要你画一个 A、B、C 三个数组的示意图，在 B[j] 处画一条竖线，左边是 A 中所有更小的元素，右边是 C 中所有更大的元素，答案的形态就一目了然了。这是我从一个整理错题本的经历中学到的：与其反复看别人的题解，不如自己画几遍图，把数量关系的结构刻在脑子里。

关于练习方法，我建议你按这个顺序做：

• 第一遍：只写暴力三重循环，用小 n 的数据验证自己对题意的理解。
• 第二遍：写排序 + 二分版，并跟暴力版对拍，确保答案一致。
• 第三遍：如果值域允许，写前缀和版，对比时间差异。
• 第四遍：尝试写双指针版，理解算法之间的内在联系。

对拍是竞赛选手最常用的调试手段之一。你可以写一个数据生成器，随机生成小规模数据，然后同时跑暴力版和优化版，比较输出结果是否一致。不一致就说明你的优化版有边界问题。这个过程比单纯对着代码发呆高效得多。

最后再分享一个小技巧：在 C++ 中把using ll = long long;定义好并且把所有计数量都声明为 ll，能省去很多强转的麻烦。虽然看起来不够“精致”，但比赛时稳比好看重要。递增三元组这道题说难不难，说简单也不简单，它考察的是你是否具备把一个直观的暴力解法升级成高效算法的能力。这个能力只能慢慢积累，希望这篇拆解能帮你迈过这道坎。