1. 先说这题到底在考什么2022 年蓝桥杯省 A 的推导部分和在洛谷上标的是普及但真正做起来很多选手第一眼觉得是前缀和模板题看完样例直接开写结果越写越不对劲。这道题表面上是给你一堆区间和的信息问你另一些区间和能不能推出来骨子里却是标准的图论建模你得把每个区间和变成两个前缀和之间的差值再把已知条件变成图中的带权边最后用带权并查集在线回答查询。说句实话这道题对思维的要求远高于对代码的要求建模想通了代码不到 80 行。先简述一下题目在干嘛。有一个长度为 n 的数组但是不给你整个数组只给你 m 条约束每条约束形如区间 [l, r] 的和等于 s。然后给你 q 个询问每个询问也是一个 [l, r]如果根据已知约束能唯一推出这个区间和就输出这个值推不出来就输出 UNKNOWN。n、m、q 都能到 1e5 这个量级所以暴力去解方程组、枚举每个 a_i 都是不可能的。哪怕是把约束当线性方程硬消元复杂度也完全不可接受。适合看这篇内容的人很明确准备蓝桥杯 C/C 组、Java 组或 Python 组的选手尤其是想弄懂带权并查集这个进阶数据结构的另外就是刷图论题但总觉得图论和我做的前缀和有什么关系的人。这道题正好把前缀和、区间和、并查集、图论串在一起是一个性价比非常高的思维训练题。下面我从读题建模开始逐步拆到代码实现和调试心得尽量把我自己踩过的坑都写清楚。2. 题意拆解为什么普通前缀和救不了你2.1 残缺的信息不能用现成前缀和直接处理如果题目把整个数组 a 告诉你了那区间和就是 pre[r] - pre[l-1]这是最基础的前缀和。但这道题偏偏只给部分区间和a 的很多值完全未知。举个最简单的例子只知道 [2, 3] 的和是 8你根本不知道 a[2] 是多少、a[3] 是多少只知道这两个加起来是 8。普通前缀和表格根本建不出来因为 pre[1]、pre[2] 这些值本身就不确定。这时候如果把所有约束看成线性方程呢n 个未知数 a[1]...a[n]m 个方程每个方程是若干 a 的和等于某个值。理论上可以用高斯消元判断某个线性组合能不能被推出但那是 O(n^3) 级别的而且 n、m 到 1e5 时连存储都没法做。这条路也死了。需要换一个完全不关心 a_i 具体值、只关心前缀和之间的差值的视角。这就是这道题最关键的一步。2.2 核心公式区间和等于两个前缀和之差设 pre[0] 0pre[i] 表示前 i 个元素的和那么任意区间 [l, r] 的和可以写成sum(l, r) pre[r] - pre[l-1]题目给出一条约束 (l, r, s)本质就是在说pre[r] - pre[l-1] s也就是说每一条已知信息不是在告诉你某个 a_i 是多少而是在告诉你两个前缀和之间差多少。反过来一个询问 (l, r) 问的就是pre[r] 比 pre[l-1] 大多少如果从已知条件能推出这个差值就输出否则 UNKNOWN。举个例子。假设真实数组是 a [2, 3, 5]那么 pre [0, 2, 5, 10]。已知 [2, 3] 的和为 8这条约束就是 pre[3] - pre[1] 8我们可以记成节点 1 到节点 3 差 8。已知 [1, 2] 的和为 5就是 pre[2] - pre[0] 5记成节点 0 到节点 2 差 5。现在问 [1, 3] 的和也就是 pre[3] - pre[1] 是多少直接由第一条约束得到 8所以可推。但问 [1, 2] 的和也就是 pre[2] - pre[1]虽然 pre[2] 相对 pre[0] 已知pre[3] 相对 pre[1] 已知但 pre[0] 和 pre[1] 之间的关系没给所以推不出来答案是 UNKNOWN。这就是推导二字的含义不是计算而是根据关系推导。2.3 每个条件是图里的一条带权边把 0 到 n 这 n1 个节点看成 pre[0] 到 pre[n]那么每条已知约束 (l, r, s) 就是节点 l-1 和节点 r 之间的一条无向的带权关系边权值为 s含义是 pre[r] - pre[l-1] s。反向来看pre[l-1] - pre[r] -s所以如果我们在图上走反向边权值要取相反数。这样一来题目就变成了纯粹的图论问题已经给出若干条带权边表示两个点的相对差值。询问任意两个点是否在同一连通块内。如果在同一连通块它们之间的差值是多少如果不在UNKNOWN。为什么可以这样做因为等式关系是可传递的。比如有 pre[b] - pre[a] x 和 pre[c] - pre[b] y就能推出 pre[c] - pre[a] x y。在图上这就是沿着 a - b - c 这条路径把两条边的权相加。等价关系天然对应图的连通性。题目保证所有约束之间没有矛盾也就是说同一个连通块内任意两条从 x 到 y 的路径算出的差值一定相同所以我们只需要维护连通性和一条路径上的权值累计。到这一步图论 前缀和两个标签就都对上了前缀和负责把区间变成点对图论负责把约束变成边剩下的问题是数据结构能多快地维护两点是否连通和连通时差值是多少。3. 带权并查集最顺手的维护工具3.1 为什么不是每次现场 BFS/DFS理论上把所有约束当作无向带权图然后预处理每个连通块给每个点赋一个相对某个基准的 pre 值查询时直接看两点是否同块、相减即可。这个思路完全正确复杂度 O(n m q)也能过这道题。但在竞赛里大多数人更推荐带权并查集weighted union-find原因有三点代码更短不需要建邻接表、写 BFS/DFS几十行搞定。约束是边来一条合并一次天然在线不需要等全部读完再建图。带权并查集本身就是维护两点之间差值关系的利器理解之后很多题都能直接用。带权并查集本质上就是并查集每个节点多存一个权值专门用来表示该节点和它父节点之间的差值。它与普通并查集唯一的区别在于路径压缩时除了把父指针指向根还要把权值同步累加合并两个集合时除了把根接上还要算清楚接上的这个根的权值。3.2 权值到底存什么约定必须统一先定一个贯穿全文的约定。数组 fa[x] 存 x 的父节点额外开一个 long long 数组 val[x]表示val[x] pre[x] - pre[fa[x]]也就是 x 相对它父节点的差值。对于根节点 rootfa[root] rootval[root] 0。这个约定的好处是如果 x 的根是 root经过路径压缩后 fa[x] 直接指向 root此时 val[x] 就变成了val[x] pre[x] - pre[root]那么对于同一个集合里的两个节点 x 和 y它们都以 root 为基准就有pre[y] - pre[x] (pre[y] - pre[root]) - (pre[x] - pre[root]) val[y] - val[x]所以查询 [l, r] 时答案就是 val[r] - val[l-1]。很多同学做带权并查集题目时最喜欢问为什么我写出来样例都不对十有八九是权值方向约定没统一。比如有人约定 val[x] pre[fa[x]] - pre[x]那后面的 find 和 merge 公式全会变。其实方向本身没有对错之分但你选了一种就必须从头到尾用到底中途换思路必乱。我的建议是代码里写注释val[x] 表示 x 比父亲大多少。3.3 find 路径压缩时权值怎么累加先看经典递归实现int find(int x) { if (fa[x] x) return x; int root find(fa[x]); // 先递归压缩父节点所在的链 val[x] val[fa[x]]; // 此时 fa[x] 还是旧父但它已经是根链上被压缩好的节点 return fa[x] root; // 最后把父指针直接指向根 }这里有一个容易蒙的点为什么递归回来之后 val[fa[x]] 就已经是旧父到根的距离了因为递归调用 find(fa[x]) 时参数是旧父节点的编号递归内部会把旧父节点的 fa 和 val 全部更新好。我们这层里的 fa[x] 变量仍然存着那个旧父节点的编号并没有被修改所以取 val[fa[x]] 就是取旧父节点到根的差值。加上 val[x] 本身是x 到旧父的差值累加自然就是x 到根的总差值。看一个真实例子会更清楚。假设集合里有 0 - 2 - 3 这样一条关系链fa[0] 2fa[2] 3fa[3] 3。初始 val[0] -5val[2] -5val[3] 0表示 pre[0] - pre[2] -5pre[2] - pre[3] -5。现在执行 find(0)递归 find(2)进入 find(2) 后继续 find(3)3 是根。回到 find(2)root 3val[2] val[fa[2]] 即 val[2] val[3]val[2] -5fa[2] 3。回到 find(0)root 3val[0] val[fa[0]]。注意这里 fa[0] 还是 2但节点 2 已经刚被更新成到根 3 的差值 -5所以 val[0] -5 (-5) -10fa[0] 3。最终 val[0] -10正好等于 pre[0] - pre[3]。一次 find 就把整条路径压缩完毕。3.4 merge 合并时权值公式到底怎么推合并操作是这道题最难写对的地方。已知一条新约束 pre[y] - pre[x] d现在要把 x 所在的集合和 y 所在的集合合并。设 rx find(x)ry find(y)分类讨论如果 rx ry说明 x 和 y 已经在一个集合里新约束只是又告诉我们一次关系。题目保证数据无矛盾所以直接忽略即可如果题目可能自相矛盾这里还要检查 val[y] - val[x] 是否等于 d不等就是矛盾。如果 rx ! ry就要选一个根当另一个根的父亲并给被挂上的根设置权值。我习惯把 rx 挂到 ry 下面也就是 fa[rx] ry。然后需要算 val[rx]即 pre[rx] - pre[ry] 等于多少。利用手头已知的信息来推根据定义pre[x] pre[rx] val[x]pre[y] pre[ry] val[y]。这里要理解为什么val[x] 是 pre[x] 相对于 pre[rx] 的差路径压缩后小小的 x 已经直接指向 rx所以上式成立。已知 pre[y] - pre[x] d代入(pre[ry] val[y]) - (pre[rx] val[x]) d展开整理pre[ry] - pre[rx] d - val[y] val[x]但我们想要的是 val[rx] pre[rx] - pre[ry]所以两边取反val[rx] pre[rx] - pre[ry] val[y] - val[x] - d这就是代码里的核心一行fa[rx] ry; val[rx] val[y] - val[x] - d;如果你喜欢把 ry 挂到 rx 下面即 fa[ry] rx那同样方法可以推出 val[ry] d val[x] - val[y]。这个公式不用背考场上花 20 秒从定义推一遍最稳。我见过太多同学背公式背错了方向样例全挂最后对着屏幕怀疑人生。4. 完整参考代码与逐段解析4.1 C17 参考代码下面这份代码是我用于这道题的标准写法实测在 1e5 数据下没有压力。#include bits/stdc.h using namespace std; using ll long long; const int N 100005; int n, m, q; int fa[N]; ll val[N]; // val[x] pre[x] - pre[fa[x]] int find(int x) { if (fa[x] x) return x; int root find(fa[x]); val[x] val[fa[x]]; return fa[x] root; } // 添加约束pre[y] - pre[x] d bool add(int x, int y, ll d) { int rx find(x), ry find(y); if (rx ry) { // 本题数据保证无矛盾可不做检查 // 若需要判矛盾可在此判断 val[y] - val[x] ! d return true; } fa[rx] ry; val[rx] val[y] - val[x] - d; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m q; for (int i 0; i n; i) { fa[i] i; val[i] 0; } for (int i 0; i m; i) { int l, r; ll s; cin l r s; // sum[l, r] s pre[r] - pre[l-1] s add(l - 1, r, s); } while (q--) { int l, r; cin l r; int x l - 1, y r; if (find(x) ! find(y)) { cout UNKNOWN\n; } else { cout val[y] - val[x] \n; } } return 0; }4.2 代码里的几个关键决策第一节点从 0 到 n共 n1 个因为 pre[0] 必须存在。初始化循环是for (int i 0; i n; i)不是i n。很多人漏掉 0 号节点导致 [1, r] 这类区间的 l-1 0 时直接越界或逻辑错误。第二读入一条约束时写成add(l - 1, r, s)因为公式里是 pre[r] - pre[l-1]。名字上用 x 表示 l-1、y 表示 r能让自己少犯到底谁是 x 谁是 y的糊涂错误。第三val 必须用 long long。区间和 s 可以很大多个差值累加后可能超过 int 范围。我见过有人 AC 了 80% 的测试点砸在一组大 s 数据上就是 int 溢出。第四查询时先find(x)再find(y)这个调用不能省。虽然并查集在 add 过程中已经做过路径压缩但有些节点可能还没有被重新访问val 暂时只表示到旧父亲的差不是到根的差。find 之后 val 才被统一成到根的差此时才能直接做减法。4.3 Python 选手怎么改如果用 Python 交蓝桥杯思路一样但要特别注意递归上限问题。并查集的 find 递归在极端情况下深度可以达到链长 1e5默认递归深度不够用所以要么加sys.setrecursionlimit(1 20)要么写迭代版 find。迭代版我推荐这个写法import sys sys.setrecursionlimit(1 20) n, m, q map(int, input().split()) fa list(range(n 1)) val [0] * (n 1) def find(x: int) - int: if fa[x] x: return x root find(fa[x]) val[x] val[fa[x]] fa[x] root return root如果担心递归常数用迭代版def find(x: int) - int: if fa[x] x: return x path [] while fa[x] ! x: path.append(x) x fa[x] root x for node in reversed(path): val[node] val[fa[node]] fa[node] root return root迭代版的思路是把沿途节点先收集起来再从靠近根的位置往外更新。每次更新时fa[node]都已经是更新过的节点因为reversed(path)保证了靠近根的节点先处理。Python 输入输出量大时记得用sys.stdin.buffer.read()一次性读入再切分或者用input()sys.stdout.write缓冲输出。蓝桥杯 Python 组在数据量较大的题上输入输出 IO 方式对最终得分影响很明显别在小地方丢分。5. 排坑日志常见的错误与定位方法5.1 症状样例都不对输出全是负的或乱值十个里面有八个是 merge 公式方向搞反。建议用一个极小的自造数据手推一遍数组 [2, 3, 5]约束 [1, 2] 5也就是 pre[2] - pre[0] 5。手动跑add(0, 2, 5)rx 0, ry 2fa[0] 2val[0] val[2] - val[0] - 5 -5。这里 val[0] pre[0] - pre[2] -5 是正确的因为 pre[0] 0pre[2] 5。如果你得到的 val[0] 5那方向就反了。再验证查询问 [1, 2] 的和即 pre[2] - pre[0]x 0, y 2答案 val[2] - val[0] 0 - (-5) 5。如果输出 -5说明查询时减的顺序错了。查询永远用val[y] - val[x]对应pre[y] - pre[x]不要习惯性地写val[x] - val[y]。5.2 症状小样例能过大样例 UNKNOWN 特别多很可能是 find 压缩后没有正确更新某些节点或者初始化时 0 号节点没设好。特别注意fa[0] 0; val[0] 0;必须存在。否则 [1, r] 这种区间涉及 pre[0]一旦 0 号没初始化find(0) 会访问未定义行为。另外检查读入顺序。题目先给 m 个约束再给 q 个询问有人会顺手写反。如果两个量都读成了先 q 后 m后面的数据就会错位症状就是输出大量 UNKNOWN 或者异常值。5.3 症状部分测试点 WA怀疑是 long long区间和 s 的范围可以很大累加路径差值也可能很大。把 val、输入变量全部声明成 long long不要只把数组开成 long long 但读入的 s 用 int。这种一半 AC 一半 WA的锅通常都是类型范围。5.4 常见问题速查表现象可能原因排查办法样例全错val 方向或 merge 公式方向反了用单元素区间 [i, i] 自测手推 val样例能过大数据 UNKNOWN 多l、r 下表转换错误确认 add(l-1, r, s) 和 query(l-1, r)部分 AC 部分 WAint 溢出所有数值变量换成 long long偶发越界数组只开到 n 而不是 n1数组大小 N 题目上界 3初始化到 n输出大量 0查询前没 find先 find 再相减或先判断 find(x) find(y)Python 递归栈溢出默认递归深度不够setrecursionlimit 或迭代版 find5.5 一套可靠的自测样例我刷题时习惯准备一组包含所有情况的迷你数据数组 [2, 3, 5]pre [0, 2, 5, 10]约束[1, 2] 5[2, 3] 8这组约束分别对应 pre[2] - pre[0] 5 和 pre[3] - pre[1] 8询问 [1, 3]pre[3] - pre[1] 8可推出输出 8询问 [2, 2]pre[2] - pre[1]因为 pre[1] 和 pre[2] 不在同一关系块里输出 UNKNOWN再补一条约束 [1, 1] 2即 pre[1] - pre[0] 2三个集合就全连通了。这时再问 [2, 2]pre[1] 2pre[2] 5输出 3。多跑这几步可以一次性验证 find 的路径压缩和 merge 的权值更新是否都正确。6. 从这道题带走的通用建模思维6.1 看到区间和 部分已知就先写 pre 公式以后在任何题里看到区间和三个字第一反应永远是sum(l, r) pre[r] - pre[l-1]而不是直接去求原数组。这道题最值钱的地方就在这一步把区间的信息变成点对的关系。一旦完成了这个转换后续用什么数据结构都是自然的事。区间已知一部分、查询另一部分本质上就是维护点对之间的相对关系这是带权并查集的经典使用场景。6.2 和差分约束系统的关系如果约束不是等于 s而是大于等于 s或者小于等于 s模型就变成差分约束系统这时需要用最短路/最长路来判断可行性不能再用并查集。但这道题的条件全是等式而等式关系恰好在图上的表现是无向的、可传递的所以并查集足够。理解这个边界以后遇到类似的题就知道什么时候该上 SPFA、什么时候该上并查集。6.3 同类题目和进阶方向带权并查集在竞赛里有几个特别典型的练习题强烈建议顺着刷洛谷 P1196 [NOI2002] 银河英雄传说经典带权并查集维护两个点之间的舰队数量差比这道题更直白。洛谷 P2024 [NOI2001] 食物链带权并查集维护模 3 的关系权值不再是差值而是类别的余数。HDU 3038 How Many Answers Are Wrong和本题几乎是同一模型只是多要求判断约束之间是否矛盾适合练合并时检测冲突。刷完这三题你会发现 P8779 的代码模板能直接迁移过去区别只在于 merge 的权值公式和冲突检测逻辑。6.4 对蓝桥杯备赛的小建议蓝桥杯省赛 A 组的题很少考那种背模板就能过的纯数据结构题反而特别爱考基础算法 一点建模变形。这道题就是典型前缀和是基础并查集是基础但把两者通过区间和 前缀和之差结合起来就能过滤掉一大批人。2026 年的蓝桥杯选手如果想把这类题吃透建议把 2022 年省赛 A 组的题目整体过一遍尤其是这道和它的配套题理解命题人是怎么把数学变形藏进数据结构的。另外蓝桥杯的真题在官网上都有历年省赛题单和题解也很全。刷题时不要只看题解一定自己把 merge 公式推一遍、手写几组小数据验证这个习惯比多做十道题都有用。最后说一点我个人的体会。带权并查集这个数据结构代码模板网上到处都是但真正决定你能不能 AC 的从来不是背模板而是权值方向、下标转换、类型范围这三样。我自己第一次做这道题时就是假设公式背住了结果 l-1 和 r 的映射写反样例都过不了。后来老老实实拿纸笔推了三次合并公式把val[x] 表示 x 比父亲大多少写在注释第一行从此再没在这类题上翻车。建议你也试试这个方法公式不熟就现场推下标不定就画坐标轴十分钟的草稿纸能省下一下午的调试时间。