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 longC或 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二分计数具体操作分三步对 A 和 C 分别升序排序。遍历数组 B 的每一个元素 b。在排好序的 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; vectorint 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_boundbisect_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 中有元素等于 xbisect_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; vectorint 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]; vectorint cntA(MAXV 5, 0), cntC(MAXV 5, 0); for (int x : a) cntA[x]; for (int x : c) cntC[x]; vectorlong 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 二分法和前缀和法的对比我在实际练习中会刻意把两种解法都写一遍因为这是很好的思维训练。总结对比一下对比维度排序二分法前缀和计数法时间复杂度O(n log n)O(n maxV)空间复杂度O(n)O(maxV)对值域要求无值域有限且可开数组实现复杂度简单需注意下标偏移和边界判断适合场景通用、稳妥数据范围有明显值域约束时你可能会想“前缀和法明明更快为什么不总用它”原因就是它太吃值域。如果值域是 10⁹数组都开不了强行离散化又回到了排序二分的老路。所以实际比赛中我最先想到的永远是二分法只有看到值域约束特别友好的时候才切换到桶法。5. 常见错误与调试技巧实录5.1 排序导致的“下标错位”问题我刚开始刷这道题时犯过一个很傻的错误先把 A、B、C 三个数组都排序了然后固定的是排序后的 B[j]。表面看起来没问题但如果你做了任何基于原始下标比如同时取 A[i] 和 B[j] 的下标去做某种映射的操作排序会直接破坏下标对应关系。这道题虽然不需要下标对应但很多变种题需要。所以建议只排序 A 和 CB 保持不变这样语义清晰也不容易引发后续踩坑。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] ≥ bpa 就是小于 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能省去很多强转的麻烦。虽然看起来不够“精致”但比赛时稳比好看重要。递增三元组这道题说难不难说简单也不简单它考察的是你是否具备把一个直观的暴力解法升级成高效算法的能力。这个能力只能慢慢积累希望这篇拆解能帮你迈过这道坎。