看到《HJ115 小红的区间构造》这个题名做过 OJ 的朋友应该能立刻嗅到一股“并查集 前缀和”的味道。区间构造类题目在各大题库里出现频率相当高题面要么让小红构造一个数组要么让小红判断一组区间约束是否能同时满足名字换了一茬又一茬核心骨架往往没变过。这道题的核心考点根本不是暴力去填数而是判断约束系统有没有解以及如何高效还原出一组可行解。这篇文章我会从题目模型说起把“区间和约束”如何转成“前缀和差值约束”讲透接着手把手拆解带权并查集的推导过程给出可直接提交的完整代码再把下标偏移、find 顺序、无解检测这几个高频坑挨个点名。无论你是准备比赛、刷题还是单纯想搞懂这类“构造 约束”题目的通用解法这篇都能直接当作参考笔记用。1. 题目理解HJ115 到底在考什么1.1 经典题目模型还原HJ115 在不同 OJ 上给出的题面措辞会有差异但骨架基本是同一个给定一个长度为 n 的数组初始内容未知给出 m 条区间约束每条约束形如“区间 [l, r] 内所有元素的和必须等于某个整数 x”要求构造出一个满足全部约束的整数数组如果无解则输出 -1。我自己通常会把输入格式整理成下面这样第一行n m 接下来 m 行每行三个整数 l r x 表示 sum(a[l..r]) 必须等于 x 输出一行 n 个整数代表构造出的数组 a有的版本还会加点附加条件比如要求数组元素非负、要求字典序最小、限制数值范围等。这些附加条件确实会增加难度但只要掌握了基础模型附加条件大多是在基础构造结果上做二次调整。1.2 为什么暴力思路一定走不通拿到这类题第一反应可能是先把数组全置 0然后对每个区间做加法把区间和凑出来。这个思路在约束少的时候可以糊弄过去一旦 n 和 m 都到 10^5 量级暴力区间修改本身就是 O(nm)更何况还要处理约束之间的冲突与回溯。更麻烦的是区间约束是全局性质的。你为了满足区间 A 调整一个位置的值可能同时破坏了区间 B 和 C。想用局部贪心去修修补补往往越补越乱。这也是“构造”类题目和“模拟”类题目最大的区别模拟题跟着题意走就行构造题必须先找到约束之间的数学关联然后一次性生成整个解。1.3 出题人真正想考察的思维区间和题目的第一性原理只有一个前缀和。任意区间和都可以写成两个前缀和的差这是处理区间统计类问题最经典的手段。一旦把区间约束改写成前缀和之间的关系问题就从“构造数组”变成“构造一组满足若干等式约束的前缀和变量”而约束也从“区间尺度”降维到了“点与点之间的差值尺度”。这个转化做完之后剩下的事情就非常清晰了m 条等式约束等价于一张图上的 m 条“带权边”要求每个点的点权满足所有边给出的固定差值。判断这张图上的差值约束是否自洽以及还原一组满足条件的点权正是带权并查集的主场。2. 核心思路区间约束如何变成点约束2.1 前缀和的三行推导定义前缀和数组 S令 S[i] a[1] a[2] ... a[i]特别地 S[0] 0。那么区间 [l, r] 的元素和有这个恒等式sum(a[l..r]) S[r] - S[l-1]这个式子没有任何高深之处但它把“一段连续区间的和”这个整体信息变成首尾两个端点的差值。于是一条输入约束 (l, r, x) 就等价于S[r] - S[l-1] x注意这里出现的节点是 r 和 l-1不是 l。下标偏移是这个模型最容易出错的地方后面我会专门讲。2.2 把约束网络看成一张带权图现在把每个前缀和 S[i] 看成图上的一个节点节点编号从 0 到 n。每条约束 (l, r, x) 就是从节点 l-1 指向节点 r 的一条有向边边上带的权值 x 表示“终点的前缀和减去起点的前缀和等于 x”。这样全部约束就形成了一张包含 n1 个节点的图。如果这是一张静态图判断自洽性的朴素做法是对每个连通分量做一遍 DFS 赋权边权冲突就说明无解。但比赛场景下约束是动态读入的而且经常需要在线合并关系、验证冲突这时候并查集的优势就体现出来了。2.3 与差分约束问题的区别很多初学者会把这个模型和差分约束搞混。差分约束处理的是形如 S[r] - S[l-1] x 的不等式约束解法是建图跑最短路遇到负环就是无解。而 HJ115 这种题面的核心词是“等于”属于等式约束。等式约束相对不等式约束更特殊完全可以用带权并查集在线合并不需要动用 SPFA。对比一下两种模型能更好地理解为什么带权并查集是这道题的正解。约束类型数学表达推荐解法复杂度等式约束S[r] - S[l-1] x带权并查集O(m log n)不等式约束S[r] - S[l-1] x差分约束 SPFAO(nm) 级别不等式约束S[r] - S[l-1] x差分约束 最长路O(nm) 级别等式约束用带权并查集本质上是把“两个点的差值已知”这件事维护成集合关系在线判断冲突效率高出 SPFA 一个量级。3. 带权并查集处理区间约束的核心算法3.1 多维护一个 d 数组普通并查集维护的是“哪几个点在同一个集合里”带权并查集在普通并查集的基础上额外维护每个节点到其父节点的差值。代码上通常这样声明const int N 1e5 5; int fa[N]; // 父节点 long long d[N]; // d[x] 表示 S[x] - S[fa[x]]d[x] 的含义要反复确认它是当前节点 x 相对于父节点的差值不是相对于根节点的差值。路径压缩完成之后由于父节点已经指向根节点d[x] 才会变成 x 相对根节点的差值。这是后面所有推导的基础也是最容易写错的地方。3.2 路径压缩的更新顺序带权并查集的 find 函数不是简单地返回根节点它必须在递归回溯的过程中累加差值。标准写法是这样int find(int x) { if (fa[x] x) return x; int root find(fa[x]); d[x] d[fa[x]]; return fa[x] root; }这里有两个关键细节。第一必须先递归调用 find(fa[x])拿到根节点之后再去更新 d[x]因为递归返回时 d[fa[x]] 已经被更新成 fa[x] 相对根节点的差值了此时累加才能得到 x 相对根节点的差值。如果顺序写反比如先更新 d[x] 再递归更新用的还是旧值结果就完全错乱。第二d[x] 的类型必须是 long long差值可正可负累计多次之后可能超出 int 范围这个后面细说。3.3 合并集合时的关键推导假设读入一条约束 S[y] - S[x] k先执行 rx find(x)ry find(y)。路径压缩之后d[x] 表示 S[x] - S[rx]d[y] 表示 S[y] - S[ry]。如果 rx 和 ry 相等说明 x 和 y 已经在同一个连通分量里它们的差值已经由之前的约束确定了。此时直接验证if (d[y] - d[x] ! k) - 无解这个式子的正确性在于根节点相同两者相减时根节点的 S 值恰好抵消。如果 rx 不等于 ry就要把两个集合合并。最常见的操作是把 rx 挂到 ry 下面也就是说要设置 fa[rx] ry然后算出 d[rx] 的数值。d[rx] 的定义是 S[rx] - S[ry]需要根据已知条件推导出来。由 d[x] S[x] - S[rx] 可得 S[x] S[rx] d[x]。 由 d[y] S[y] - S[ry] 可得 S[y] S[ry] d[y]。 代入约束 S[y] - S[x] k(S[ry] d[y]) - (S[rx] d[x]) k S[ry] - S[rx] k d[x] - d[y] S[rx] - S[ry] d[y] - d[x] - k最后得到d[rx] d[y] - d[x] - k这一步推导是整个算法的灵魂。很多人背了公式但不知道为什么真到变式题就懵。建议自己动手推一遍把 S[rx] 和 S[ry] 用 d 数组表示出来等式两边整理一下结论自然就出来了。3.4 合并函数完整实现把上面的逻辑组装成一个 bool 函数返回 false 表示这一条约束与已有约束冲突bool merge(int x, int y, long long k) { // 约束S[y] - S[x] k int rx find(x), ry find(y); if (rx ry) { return d[y] - d[x] k; } fa[rx] ry; d[rx] d[y] - d[x] - k; return true; }如果倾向把 ry 挂到 rx 下面公式会变成 d[ry] d[x] k - d[y]也能推出同样的效果。关键是挂载方向一旦确定d 的赋值公式必须和挂载方向配套不要混着用。4. 完整实现与构造还原4.1 主流程设计处理完整道题我习惯按四步走这个流程对几乎所有“等式约束 构造数组”的题目都适用。第一步初始化并查集。注意节点范围是 0 到 n一共 n1 个节点fa[i] id[i] 0。这里不能只初始化 1 到 n因为约束会用到 l-1当 l1 时需要访问节点 0。第二步逐条读入约束并调用 merge。merge 返回 false 时标记冲突但不要立刻 break 跳出循环先把剩余输入读完再统一输出 -1。虽然很多 OJ 是一次性读入不 break 也能过但养成这个习惯可以避免在交互式题目里踩坑。第三步全部约束处理完之后如果没有冲突开始构造前缀和数组 S。做法是先对每个节点执行一次 find拿到根节点和相对根节点的差值 d[i]。然后给每个根节点确定一个基准值所有节点的实际前缀和就是基准值加 d[i]。第四步由 S 还原数组 aa[i] S[i] - S[i-1]输出即可。4.2 可提交的 C 代码这里给出一份完整的参考实现注释里标了每一步的关键逻辑。#include bits/stdc.h using namespace std; const int N 1e5 5; int fa[N]; long long d[N]; int find(int x) { if (fa[x] x) return x; int root find(fa[x]); d[x] d[fa[x]]; return fa[x] root; } bool merge(int x, int y, long long k) { // 约束S[y] - S[x] k int rx find(x), ry find(y); if (rx ry) { return d[y] - d[x] k; } fa[rx] ry; d[rx] d[y] - d[x] - k; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; for (int i 0; i n; i) { fa[i] i; d[i] 0; } vectortupleint, int, long long cons; cons.reserve(m); bool ok true; for (int i 0; i m; i) { int l, r; long long x; cin l r x; cons.emplace_back(l - 1, r, x); // 注意转换为 l-1 if (ok) { if (!merge(l - 1, r, x)) ok false; } } if (!ok) { cout -1 \n; return 0; } // 先统一 find保证 d[i] 代表 S[i] - S[root] for (int i 0; i n; i) { find(i); } unordered_mapint, long long base; int r0 find(0); base[r0] -d[0]; // 让 S[0] 0符合前缀和定义 vectorlong long S(n 1); for (int i 0; i n; i) { int r find(i); if (base.find(r) base.end()) { base[r] 0; // 其他连通分量整体加任意常数都不影响区间和 } S[i] base[r] d[i]; } for (int i 1; i n; i) { cout S[i] - S[i - 1] (i n ? \n : ); } return 0; }关于构造 S 这里有个非常容易困惑的细节S[0] 到底要不要强制为 0我的做法是把 0 所在连通分量的根基准设为 -d[0]这样算出来的 S[0] 严格等于 0和前缀和的定义完全一致。对于其他连通分量根基准取 0 即可。可能有人会担心不同连通分量的基准取值会不会导致区间约束失效完全不会因为每条约束涉及的节点都在同一个连通分量内分量整体平移时差值 S[y] - S[x] 保持不变。4.3 手动走一个样例写代码容易但真正理解合并过程还是得手动过一遍样例。我拿一个小数据推给大家看。假设 n5约束有下列三条[2, 4] 的和为 6 [1, 3] 的和为 3 [2, 5] 的和为 5转化为前缀和约束分别是S[4] - S[1] 6 S[3] - S[0] 3 S[5] - S[1] 5第一条约束合并节点 1 和 4令根节点连续d[4] 6默认根取节点 1S[1]0 时 S[4]6。第二条约束将节点 0 和 3 合并为另一个分量。第三条约束回来找节点 1 和 5节点 1 已经在第一个分量于是把节点 5 也挂进去d[5] 5。处理完没有冲突。此时令 S[0] 0那么 S[3] 3再给第一个分量的根设基准为 S[1] 1或者任意值则 S[4] 7S[5] 6。取 S[1] 1 之后S[2] 可以任取比如取 2。于是递推数组 aa[1] S[1] - S[0] 1 a[2] S[2] - S[1] 1 a[3] S[3] - S[2] 1 a[4] S[4] - S[3] 4 a[5] S[5] - S[4] -1验证一下a[2] 到 a[4] 是 1 1 4 6a[1] 到 a[3] 是 1 1 1 3a[2] 到 a[5] 是 1 1 4 - 1 5。和输入的三条约束完全吻合。5. 常见问题与排查技巧实录5.1 下标偏移为什么是 l-1 而不是 l这是区间和转前缀和时最经典的坑。区间 [l, r] 的和等于 S[r] - S[l-1]很多初学者会下意识写成 S[r] - S[l]导致整个构造结果虽然自洽但和题目要求差了一个元素。建议在读入后立刻统一转换成节点 u l-1v r后续所有逻辑只管 u 和 v不再管原始的 l 和 r彻底避免混淆。5.2 find 之后再取 d 是强制动作带权并查集里d[x] 在没有执行 find 之前表示的是 x 相对父节点的差值。如果父节点自己也有父节点那 d[x] 就不是相对根节点的值。很多人拿到 rx 和 ry 之后直接比较 d[v] - d[u] 和 k 是否相等结果在非根集合上永远验证出错。正确做法是先调用 find(x) 和 find(y)确保 d[x] 和 d[y] 都是相对各自根节点的差值再进行后续判断。5.3 同集合判断必须放在合并之前merge 函数里必须先判断 rx ry再决定是验证还是合并。如果把判断和合并的顺序写反比如先执行挂载再判断原集合关系整个并查集的差值信息会被覆盖而且程序不会直接报错只会悄悄输出一个错误答案排查起来非常耗时。5.4 数据范围不设防的代价n 最大 10^5区间和的约束值也可能给到 10^9累加出来的 S 值很容易突破 int 的边界。我之前就吃过这个亏用 int 存 d 数组小数据测什么都对一上大数据就莫名输出错误。后来统一改成 long long问题彻底消失。建议从写第一行代码开始就用 long long不要觉得麻烦。5.5 交互式场景下不要提前 return有的题目支持边读边处理发现冲突就输出答案然后结束。但更多 OJ 是一次性输入提前 break 会导致输入流里还有残留数据影响后续行为。稳妥的做法是把所有约束先存下再来处理或者至少标记冲突后继续读完。我上面的代码就是先存一遍再统一处理虽然浪费一点点内存但逻辑干净不容易出毛病。5.6 构造 a 数组时 S[2] 这种未约束节点怎么取如果某个 S[i] 从来没有任何约束关联到它它属于一个独立的连通分量。上面代码里这种分量的根基准被设为 0也就是 S[i] 0。这在数学上完全合法因为没有任何约束会检验这个 S[i]对应的 a[i] 也仅仅是作为相邻差的一部分存在。想构造带附加条件的解时就可以在这里做文章比如通过调整未约束分量的基准值来让所有 a[i] 非负。6. 这套模型的扩展用法6.1 不带构造的纯一致性判断很多 OJ 会把这类题改成只问“约束是否冲突”不要求输出构造结果。这种题做起来更省事连最后一步还原 S 都省了直接跑完所有 merge 看有没有返回 false 就行。理解了 HJ115 的完整流程这种变式相当于白送分。6.2 反向题目区间加点权求最终数组如果把题面改成“初始数组全为 0给出 m 次操作每次把区间 [l, r] 内所有元素加上 x求最终数组”那就是另一套叫差分数组的经典技巧。这类题虽然不叫“区间构造”但思维上刚好互补带权并查集是从最终约束反推前缀和差分数组是从区间操作正推原数组。两道题放在一起学区间相关的两大工具就齐了。6.3 字典序最小这类附加要求怎么处理如果需要输出字典序最小的解核心思路是在还原 S 的阶段把约束传播到位。字典序大小本质上取决于 a[1], a[2], ... 的取值而 a[i] S[i] - S[i-1]所以可以优先固定较小的前缀和把自由度留给后面的节点。具体实现会用到贪心加优先级队列但底层仍然是带权并查集那套关系网。回到 HJ115 本身我做这题最大的体会是区间构造的难点从来不在区间而在于把区间约束降维成点约束。前缀和是降维的桥带权并查集是处理点约束的工具两者缺一不可。第一次写的时候我在 find 顺序上栽了跟头后来手推了三遍合并公式才算真正理解 d[rx] d[y] - d[x] - k 是怎么来的。建议你也把公式推一遍然后对照样例跑一遍这种扎实的推导过程比刷十道同类型题都管用。最后再分享一个我个人的做题习惯遇到这种约束构造题先把输入约束统一转化成“节点 差值”的记号写在草稿纸上再想算法。这个习惯帮我躲过了多次下标偏移的坑实测下来效率非常高。