P8779 推导部分和这道题我印象很深。题目标签写着“图论 前缀和”难度“普及”但第一次看到题目描述的时候我根本没想到这题能和图论扯上关系。给你一堆区间和的已知条件然后问另一个区间和能不能求出来、能求就输出值听起来像个纯数学推导题怎么会和并查集有关直到我把前缀和公式往题干里一代所有条件都变成了“两个前缀和之差等于某个数”图论建模的思路一下子就通了。这道题非常适合正在备战蓝桥杯省赛、NOIP普及组或者CSP-J/S的同学去啃它考察的并不是什么冷门算法而是把“区间约束”翻译成“图上的边”的能力这种建模意识在竞赛里比背一百个模板都值钱。1. 先读懂题目部分和到底在问什么1.1 题干里的三个关键要素先明确题目结构。你有一个长度为 N 的数组数组元素的值没有直接给出手里只有 M 条已知信息每条信息形如“闭区间 [l, r] 的和等于 s”。接下来有 Q 个询问每个询问也给出一个区间 [l, r]你要回答根据已知的 M 条信息能不能推导出这个区间的和如果能输出具体数值如果不能输出题目指定的字符串一般是 UNKNOWN。这里要特别注意题目不会让你还原原数组只让你求“某个区间和能不能被现有条件唯一确定”。这就意味着你不能尝试把每个元素求出来再去相加因为已知条件往往只覆盖部分区间而且区间之间互相重叠、交叉甚至绕几个弯才能凑出答案。我举个例子已知 [1,3] 的和是 10又知道 [4,5] 的和是 7那 [1,5] 的和当然就是 17这条询问不需要任何新条件就能算出来。但如果是已知 [1,3] 的和是 10[2,5] 的和是 2问你 [1,1] 的和是多少你就得做减法[1,1] [1,3] - [2,3]而 [2,3] 又能从 [2,5] 和 [4,5] 的关系里推出来。这些关系一环套一环靠肉眼根本看不过来。所以这类题的本质不是“线段树维护区间和”而是“给定若干等式约束判断两个变量之间的差值能否唯一确定”。想通这一点整道题的难度就下降了一大半。1.2 前缀和变换把区间和改成点对关系区间和问题里最经典、最朴素的工具就是前缀和。定义前缀和数组 S[i] 表示数组前 i 个元素的和特别地 S[0] 0。那么区间 [l, r] 的和可以写成S[r] - S[l-1]这是一个纯粹的代数恒等式没有任何算法含量但威力巨大。每一条已知条件“区间 [l, r] 的和是 s”就等价于“S[r] - S[l-1] s”。这样一来题目中所有的区间和条件都被改写成了两个前缀和变量之间的差值等式。于是问题就完全变形了现在我们有 N1 个变量 S[0], S[1], ..., S[N]已知若干“两个变量之差等于多少”的等式询问某两个变量 S[l-1] 和 S[r] 的差是否已经被这些等式唯一确定。这个转化是整个题目的题眼也是“前缀和”三个字出现在题目标签里的原因。后面所有图论建模全部建立在这个 S 数组之上。很多同学容易在这里犯一个低级错误把区间 [l, r] 映射成 S[l] 到 S[r]写出来的等式是 S[r] - S[l] s结果样例都过不了。因为区间 [l, r] 的和包含第 l 个元素S[l] 是前 l 个元素的和减掉 S[l] 会丢掉 A[l]正确做法是减 S[l-1]。这个下标细节我会在第 4 部分展开讲。2. 图论建模为什么会想到并查集2.1 把条件看成带权边现在我们已经有了若干个等式比如“S[r] - S[l-1] s”。在算法竞赛里遇到这种“两个变量之差恒定”的等式第一反应就是往图论上靠把每个前缀和变量看成图上的一个点把一条等式看成一条有向带权边。具体来说对于已知条件 S[r] - S[l-1] s我从节点 l-1 向节点 r 连一条权值为 s 的有向边表示从 l-1 走到 r 时S 的值增加了 s。当然等式是对称的反过来从 r 到 l-1 连一条权值为 -s 的边也完全等价。为了方便统一处理我们只记录一个方向但在推导时要注意正负号。把所有 M 条已知条件都这样转成边之后图里会出现若干个连通块。比如已知 [1,3] 的和是 10即在 S[0] 和 S[3] 之间连边已知 [4,5] 的和是 7即在 S[3] 和 S[5] 之间连边。那么 S[0]、S[3]、S[5] 就在同一个连通块里我可以直接推出 S[5] - S[0] 17对应区间 [1,5] 的和。这就是图论视角下“推导”的含义沿着已知的边在图上走出一条从起点到终点的路径把路过边权按方向累加就得到了两个前缀和变量的差值。2.2 推导部分和的本质是判断连通性既然推导的过程就是在图上找路径那么一个询问 [l, r] 能不能被回答就等价于问节点 l-1 和节点 r 在不在同一个连通块里如果在同一个连通块里说明存在一条路径把 S[l-1] 和 S[r] 联系起来它们的差值可以通过路径上的边权推算出来答案就是这条路径的总权值。如果不在同一个连通块里说明没有任何等式把这两个变量关联起来哪怕拐多少个弯都碰不到一起那它们的差值就没有任何约束答案自然就是 UNKNOWN。这里有个很重要的前提对于这种“等式型”的关系图同一个连通块内任意两点之间的差值其实是唯一的。也就是说不管从 A 走到 B 走的是哪条路累加出来的权值一定相同。为什么因为每条边都对应真实存在的前缀和等式如果存在两条不同的路径推出不同的差值那就意味着已知条件之间互相矛盾实际题目数据一般不会这么设计。所以我们只需要关心“通不通”不需要关心“走哪条路”这让并查集这种专门维护连通性的数据结构成为最合适的工具。我习惯用一个生活化的类比来理解它假设班级里有身高比较记录“小红比小明高 5 厘米”“小明比小刚高 3 厘米”那我立刻知道小红比小刚高 8 厘米。但要是小红和小丽之间没有任何一条直接或间接的比较记录我就永远说不出她俩谁高、高多少。每条身高记录就是一条带权边小红的“关系连通块”里没有小丽所以无法推导。区间和问题里前缀和变量就是这些同学已知条件就是身高比较记录。2.3 带权并查集的原理普通并查集只能回答“两个点是否连通”而这里还要求“连通时两点之间的差值是多少”所以要在并查集上额外维护一个权值数组。这个数据结构的通用名字叫“带权并查集”也叫“关系并查集”。核心思想很简单在路径压缩的时候不光让每个节点直接指向根还要顺便记录“该节点到根节点的差值”。如果每个节点都知道自己和根节点的相对关系那么任意两个在同一集合内的节点就能通过“自己到根的差值”减去“对方到根的差值”来得到两者的差值。注意这里有个关键选择d[i] 到底表示“S[i] - S[parent[i]]”还是“S[parent[i]] - S[i]”。不同写法会让合并公式差一个负号所以一旦选定后面所有推导都得按同一个约定走。我在这篇题解里统一使用d[i] S[i] - S[parent[i]]这样路径压缩结束后d[i] 就是 S[i] - S[root]查询 S[b] - S[a] 时直接算 d[b] - d[a] 即可正好是区间和非常顺手。3. 代码实现带权并查集落地3.1 关键变量与约定先梳理一下代码里要维护的东西n、m、q分别表示数组长度、已知条件数量、询问数量。parent[x]x 的父节点根节点的父节点是自身。d[x]当前约定下x 到其父节点的权值即 S[x] - S[parent[x]]路径压缩后表示 S[x] - S[root]。初始化的时候节点编号从 0 到 N一共 N1 个点每个点的父节点都指向自己d 全部置 0。这一步不要漏掉节点 0因为区间 [1, r] 的条件会用到 S[0]。整个算法的复杂度接近 O((MQ)αN)α 是反阿克曼函数实际运行中基本可以看作常数。这意味着即使 M、Q 都到 10^5 甚至 10^6这个做法都能轻松跑过不需要担心性能。3.2 路径压缩与合并公式的推导先看 find 函数的写法int find(int x) { if (parent[x] x) return x; int root find(parent[x]); // 先把父节点的根找到 d[x] d[parent[x]]; // 累加x到根 x到旧父 旧父到根 return parent[x] root; // 压缩 }这里最容易写错的地方是累加的时机。你必须先递归调用 find(parent[x])把 parent[x] 压缩到根再去执行 d[x] d[parent[x]]。因为递归返回后parent[x] 已经被更新成了根节点d[parent[x]] 也已经被更新成了“旧父节点到根节点的差值”这时候累加才是正确的。如果顺序反过来或者用循环写法时先累加再向上跳算出来的权值就是错的。再看合并的公式推导。假设有一条新条件表示 S[b] - S[a] w。我分别 find(a) 和 find(b)得到 a 的根是 rab 的根是 rb。如果 ra rb说明 a 和 b 已经在同一个关系连通块里这条新条件和已有信息要么一致要么矛盾可以做矛盾检测后面扩展部分会讲。如果 ra ! rb我需要把 ra 所在集合合并到 rb 所在集合也就是让 parent[ra] rb。问题来了d[ra] 应该赋成多少此时路径压缩已经完成所以有S[a] d[a] S[ra] S[b] d[b] S[rb]把这两个式子代入 S[b] - S[a] w(d[b] S[rb]) - (d[a] S[ra]) w移项整理S[ra] - S[rb] d[b] - d[a] - w左边正是 d[ra] 的定义S[ra] - S[rb]因为 ra 的父节点要设成 rb。所以合并操作就是void merge(int a, int b, long long w) { int ra find(a), rb find(b); if (ra rb) return; parent[ra] rb; d[ra] d[b] - d[a] - w; }这个公式是整道题最容易抄错的地方。网上一搜能找到好几种写法有的 d[i] 定义是 S[parent[i]] - S[i]有的是把 rb 挂到 ra 上公式都会跟着变。我的建议是你只记住一套并且每次写代码前都自己从“S[b] - S[a] w”这个条件手推一遍熟练之后三十秒就能推完比硬背公式靠谱得多。3.3 完整 AC 代码下面给出我整理的完整代码加了必要的注释可以直接在洛谷 P8779 上提交#include bits/stdc.h using namespace std; const int MAXN 100005; int n, m, q; int parent[MAXN]; long long d[MAXN]; // 约定d[x] 表示 S[x] - S[parent[x]] // 路径压缩后d[x] S[x] - S[root] int find(int x) { if (parent[x] x) return x; int root find(parent[x]); d[x] d[parent[x]]; // 先递归后累加顺序不能反 return parent[x] root; } void merge(int a, int b, long long w) { // 已知条件S[b] - S[a] w int ra find(a), rb find(b); if (ra rb) return; parent[ra] rb; // 推导S[ra] - S[rb] d[b] - d[a] - w d[ra] d[b] - d[a] - w; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m q; // 节点编号 0..n一共 n1 个前缀和变量 for (int i 0; i n; i) { parent[i] i; d[i] 0; } while (m--) { int l, r; long long s; cin l r s; // [l, r] 的和是 s - S[r] - S[l-1] s merge(l - 1, r, s); } while (q--) { int l, r; cin l r; int a l - 1, b r; if (find(a) ! find(b)) { cout UNKNOWN\n; } else { cout d[b] - d[a] \n; } } return 0; }这段代码里有一个很微妙的点询问时我先执行了 find(a) 和 find(b)确保两个节点的 d 值都已经是“到根节点的差值”然后再做 d[b] - d[a]。如果省略掉 find 直接比较 parent可能会因为路径尚未压缩而取到不全的数据所以千万不要在查询时偷懒。4. 一边写题一边踩过的坑4.1 下标问题区间左端点要减一我前面反复强调区间 [l, r] 对应 S[r] - S[l-1]所以建边和查询的时候左端点一律先减 1。这不仅是“减不减”的问题还直接影响数组开多大。l 的最小值是 1l-1 最小是 0所以并查集里存在节点 0初始化时一定要从 i0 循环到 in而不是从 1 开始。我身边有同学第一次做这道题时把条件映射成了 S[l] 和 S[r]导致样例能蒙对一部分一到数据复杂点就全错。排查方法很简单拿区间 [1,1] 测一下如果已知 [1,1] 的和是 x询问 [1,1] 应该直接输出 x。用错误的映射方式这条就过不去。4.2 方向与正负号别搞反带权并查集写久了你会发现大部分 bug 都是符号问题。这里的根源在于你读入一条条件 (l, r, s) 后心里必须立刻锁定一个不可动摇的等式S[r] - S[l-1] s。之后无论是合并还是查询永远从这个等式出发。如果你在某处突然想“把边反过来连”或者“把减号换成加号”那恭喜你你即将获得一次错两个小时的调试体验。我自己的习惯是把这道题的数学模型写在草稿纸上写成大字贴屏幕边每次写 merge 和查询之前先看一眼确认公式里的符号一致再动手。另外提醒一点题目给的 s 可以是负数区间和并不一定是正数。所以 d 数组、输入变量都必须是 long long别为了省事开 int。4.3 输出字符串的格式别写错题目要求无法推导时输出指定字符串我记得是 UNKNOWN但不同平台、不同年份的题可能大小写或格式略有差异。提交前先看题面里的 Output 部分确认是“UNKNOWN”“Unknown”还是“unknown”。这种错误不会出现在样例里只有真正提交才会暴露很恶心。4.4 常见问题速查表我把写这道题时遇到的典型问题整理成一个表方便你对照排查问题现象可能原因解决方案样例都过不了区间左端点没有减 1统一使用 S[r] - S[l-1]小数据对大数据错d 数组开了 int全部换成 long long部分询问输出负数方向搞反或公式符号错重新从 S[b] - S[a] w 推一遍运行超时find 里累加顺序导致递归死循环先递归再累加 d[x] d[parent[x]]查询结果不对但合并没问题查询前没有先 find 压缩比较前先调用 find(a), find(b)节点越界或 RE数组只开了 n没开 n1并查集初始化到 in数组开到 n25. 从这道题延伸出去5.1 另一种写法建图 DFS 赋权带权并查集不是唯一解法。拿到所有条件后我完全可以先建一张邻接表然后对这个图做 DFS/BFS给每个点赋一个“相对权值”。具体做法是每个连通块内随便选一个点作为基准把它赋值为 0然后沿边扩展。如果有一条边表示 S[b] - S[a] w而我已经知道 S[a]就令 S[b] S[a] w。如果遇到一个点被重复访问就检查两次赋的值是否相同相同则继续不同则说明条件矛盾。这种写法的优点是更贴近“图论”直觉初学者容易理解缺点是需要把 M 条边全部存下来而且当条件在线给出时不够灵活。不过对于 P8779 这种离线题目来说DFS 赋权完全可以 AC。我建议你两种方法都写一遍用 DFS 帮助自己建立“连通块内相对值唯一”的直观感受再用带权并查集去体会动态维护的效率。5.2 向差分约束系统扩展把题目中的等式 S[r] - S[l-1] s 改成不等式 S[r] - S[l-1] ≥ s或者允许同时存在大于等于、小于等于两类约束问题就会升级成差分约束系统。差分约束的经典解法是把不等式变成带权边然后求最短路或最长路来判断可行性和求解它在任务调度、时间窗口规划等问题里应用很广。P8779 的等式模型是差分约束的一个特例因为等式是双向的所有关系都是强约束所以用并查集就能解决。一旦引入不等式图里可能出现负环就要上 SPFA 或者 Bellman-Ford。理解了这道题之后再去学差分约束你会觉得非常顺滑因为你已经熟悉了“把代数关系变成图上的边”这一整套思维。5.3 顺手加上矛盾检测合并的时候如果 find(a) find(b)说明 a 和 b 已经在同一个集合里此时它们的差值已经被确定。那么这条新条件给的 w 到底对不对只需要检查一个等式d[b] - d[a] 是否等于 w如果相等说明新条件与旧条件一致什么都没发生如果不相等说明已知信息彼此矛盾。这个功能在 P8779 的普通数据里可能用不上但在很多“判定等式系统是否自洽”的题目里就是核心考点。你可以把 merge 写成返回 bool 的形式检测到矛盾时返回 false这样这段代码立刻就能复用到别的题上。5.4 竞赛策略这题值不值得死磕蓝桥杯省赛 A 组这种“普及”难度的题目通常是省一和二等奖的分水岭。它不像压轴题那样需要复杂的优化技巧考察的是你能不能快速建模、准确实现基础数据结构。带权并查集在蓝桥杯、NOIP 提高组、CSP-S 里都是常客同模型的经典题包括“食物链”“银河英雄传说”“Parity Game”等。我建议的学习路径是普通并查集 → 带权并查集 → 差分约束。每一步都找两三道真题做透比盲目刷题有效得多。最后分享一点个人体会。我第一次独立写这道题时合并公式推了整整三遍最后还是因为 d[ra] 的符号问题错了一次。当时很挫败但后来想明白了带权并查集这种题错的从来不是算法框架而是“我自己定义的符号体系”没有被严格执行。写这类题先把 d[i] 的含义写死在注释里把合并公式从等式条件手推一遍再落笔基本能消灭八成 bug。这道 P8779 虽然只是“普及”但它把图论建模、前缀和变换、并查集进阶这三个重要考点串在了一起吃透它以后遇到再复杂的部分和问题你都不会再慌。