企业官网建设流程全解析

第一次看到 Codeforces 787D Legacy 的时候，很多人第一反应是：这不就是普通的单源最短路吗，把三类边全建出来，直接跑 Dijkstra 不就完了？然后一看 n、q 都是 1e5，老老实实逐点建边的话，光是区间边的数量就能把内存和时间一起送走。这个题之所以经典，恰恰是因为它把“区间边”这个看似棘手的结构，用线段树压缩成了 O(log n) 级别的边数，再交给最短路解决。说白了，就是线段树优化建图 + Dijkstra。

这个做法适合两类人看：一类是刚接触线段树优化建图的选手，想搞明白“为什么要建两棵树”“方向到底怎么定”；另一类是已经会套模板，但总是建图建错、样例都过不了的人。这篇文章我会把从题意拆解、建图设计、完整代码到常见坑位全部展开，尽量让你看完之后能独立写出来。

1. 题目到底在问什么

1.1 三种边的基础形态

原题的意思可以抽象成一张有 n 个点的图。除了普通的点对点边之外，还有两种特殊的“区间边”：

• 从某个点 u 连向区间 [l, r] 内的所有点，边权为 w；
• 从区间 [l, r] 内的所有点连向某个点 u，边权为 w。

起点固定为 s，要求 s 到 1 到 n 每个点的最短距离。

如果只有第一种普通边，那问题没有任何难度，裸 Dijkstra 就能过。但区间边的存在，让“建图”本身变成了主要矛盾。你不可能真的把一条“点连向区间内所有点”的边，展开成从 u 到每个点的一条边；反过来，“区间内所有点连向 u”也不可能在图上真的给每个区间内点都拉一条边到 u。数据范围一大，这就不是优化问题，而是可行性问题。

1.2 朴素建图的数据量到底有多离谱

假设 n = 1e5，q = 1e5，极端情况下每一次操作都是区间边。一个长度为 len 的区间，如果展开成点对点边，就要建 len 条边。区间平均长度可能是 n/2 级别，那么一次操作就是 5e4 条边，100000 次操作就是 5e9 条边。这还只是边数，还没算真正的 Dijkstra。

5e9 条边，哪怕是每条边只存两个 int 加一个 long long，也得几百 GB 内存。时间更不用想，Dijkstra 的复杂度是 O(E log V)，E 到这种量级，跑完一轮地球可能都转好几圈了。

所以核心矛盾很清楚：很多点明明共享同一条“区间属性”，却被我们展开成了大量平行边。如果能让一个点代表一个区间，再由这个代表点把权值“广播”到区间里的每个点，边的数量就能从 O(len) 降到 O(log n)。

1.3 线段树刚好能干这件事

线段树天然就是处理区间问题的。它可以把任意区间 [l, r] 拆成 O(log n) 个线段树节点。如果这些节点能作为“虚拟中转站”，那么我们只需要从 u 连向这 O(log n) 个节点，再从这些节点向叶子节点走 0 权边，就能覆盖区间内所有点。反过来也一样，区间内所有点可以先走到某个区间节点，再由区间节点连向 u。

但这里有一个很容易忽略的方向问题：从点到区间，和从区间到点，方向是相反的。点连向区间，需要从区间代表节点向下“扩散”到叶子；区间连向点，需要从叶子向上“汇聚”到区间代表节点。单靠一棵线段树没法同时满足这两个方向，所以需要两棵方向相反的线段树。

2. 线段树优化建图的整体设计

2.1 两棵树，方向相反

我习惯把两棵树分别叫作“出树”和“入树”，名字不重要，重要的是方向。

• 第一棵树：父节点向子节点连 0 权边。也就是说，从某个区间节点出发，可以一路走到它包含的叶子节点。这棵树用来处理“点 u -> 区间 [l, r]”的情况。因为 u 只要跳到某个区间节点，就能沿着父子关系下降到区间里任意一个点。

• 第二棵树：子节点向父节点连 0 权边。也就是说，从某个叶子节点出发，可以一路向上走到包含它的区间节点。这棵树用来处理“区间 [l, r] -> 点 u”的情况。因为区间里任意一个叶子 v，都能沿着子父关系上升到代表区间的那几个节点，再由这些节点跳到 u。

一句话记忆：点进区间，用从上往下那棵树；区间进点，用从下往上那棵树。

2.2 叶子节点直接复用原图节点编号

这是很多模板里最微妙的一点。两棵线段树的叶子，其实都对应原始图的 1 到 n 号节点。建树的时候，对于叶子位置 l，不需要新建图节点，直接让它的图节点编号等于 l 就可以。

内部节点则需要另外分配编号。因为如果内部节点编号和叶子节点编号混在一起，加边时就会把线段树内部结构搞乱。常见做法是维护一个计数器 tot，初始值等于 n，每次给线段树内部节点分配新编号时就++tot。

两棵树的叶子编号都用原节点编号，不会冲突，因为原节点本来就只有一份。真正代表区间的是内部节点，而两棵树的内部节点编号是不重叠的，由 tot 统一分配。

这样设计还有一个好处：原图节点本身就是叶子，不需要额外再连“原节点 -> 对应叶子”的 0 权边。例如从某个点 u 出发，既可以直接走普通边，也可以在第二棵树里沿着子到父的 0 权边向上走到区间节点，这正好实现了“从区间内点出发”的语义。

2.3 三类操作在图上分别怎么连边

现在三种操作都能落到“加边”上了：

第一棵树内部是父向子连 0 权边。当 u 连到某个区间节点 x 后，x 可以沿着 0 权边走遍它子树里的所有叶子，也就是区间里的所有点。

第二棵树内部是子向父连 0 权边。当区间 [l, r] 内任意一个点 v 出发时，如果 v 的叶子在区间内，那么它一定能沿着子到父的 0 权边上行到某个被拆出来的区间节点 x，再通过 x -> u 这条权值为 w 的边到达 u。

这里的关键是：不管区间内哪个点出发，都能到达那个代表它的区间节点。因为区间节点本来就是在线段树上覆盖 v 所在位置的那个节点，v 的叶子向上走，一定会经过它。

2.4 正确性：为什么不会漏，也不会多出非法路径

先说为什么不会漏。任意区间 [l, r] 在线段树上会被拆成若干个节点，这些节点两两不相交，并且覆盖了 [l, r] 内所有位置。所以区间内任意点 v，至少会被其中一个节点覆盖。点 u 连向这些节点后，必然能沿第一棵树的 0 权边到达 v；或者 v 沿第二棵树的 0 权边上行到这些节点，再到达 u。因此所有题目要求的边都存在于图上。

再说为什么不会多出不存在的路径。第一棵树的 0 权边方向是父到子，所以它只能把“区间节点”扩散成“区间内点”，不能让一个点反向汇聚到更大的区间。第二棵树的 0 权边方向是子到父，所以它只能把“区间内点”汇聚成“区间节点”，不能让一个区间节点广播到更小的子区间。两棵树的方向互相独立，不会出现从任意点出发，凭空 0 权走到全图任意点的错误路径。

即使图上因为操作边和树边组合出一些额外的路径，这些路径也只会等价于“多个区间边或普通边依次拼接”的合法路径，不会突破题目本身定义的转移规则。

3. 核心代码怎么写

3.1 图结构、id 数组和建树函数

这里先定义一个全局的图结构。因为最短路用的是 Dijkstra，而题目边权可能很大，所有距离和边权都必须用 long long。我习惯用邻接表存图：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> P; const int MAXN = 100000 + 5; const int MAXNODE = MAXN * 10; const ll INF = 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to; ll w; }; vector<Edge> g[MAXNODE]; int id[2][MAXN << 2]; // id[type][线段树数组节点] -> 图节点编号 int n, q, s; int tot; // 已分配到的图节点数量 vector<int> segNodes; // 临时存储区间拆分出的图节点编号 void addEdge(int u, int v, ll w) { g[u].push_back({v, w}); }

这里的id[0]和id[1]分别对应两棵线段树。注意数组长度要开到 4 倍 n，因为普通线段树数组下标最大可能到 4n 左右。

建树的区别只在于内部边的方向。对于第一棵树，区间节点向子节点连 0 权边；对于第二棵树，子节点向区间节点连 0 权边：

void build(int p, int l, int r, int type) { if (l == r) { id[type][p] = l; return; } int mid = (l + r) >> 1; build(p << 1, l, mid, type); build(p << 1 | 1, mid + 1, r, type); id[type][p] = ++tot; if (type == 0) { // 第一棵树：父 -> 子，权值 0 addEdge(id[type][p], id[type][p << 1], 0); addEdge(id[type][p], id[type][p << 1 | 1], 0); } else { // 第二棵树：子 -> 父，权值 0 addEdge(id[type][p << 1], id[type][p], 0); addEdge(id[type][p << 1 | 1], id[type][p], 0); } }

这里有一个容易被忽略的细节：叶子节点直接使用id[type][p] = l。也就是说，两棵树的叶子都映射到原图节点 1 到 n。如果你在叶子处也++tot新建节点，那么原图节点和叶子之间还得额外加 0 权边，建图会变得非常绕。

3.2 区间拆分函数

给定一个查询区间 [l, r]，需要把在线段树中覆盖到它的节点编号收集起来。这个函数和普通线段树的区间查询写法基本一样：

void collect(int p, int l, int r, int ql, int qr, int type) { if (ql <= l && r <= qr) { segNodes.push_back(id[type][p]); return; } int mid = (l + r) >> 1; if (ql <= mid) collect(p << 1, l, mid, ql, qr, type); if (qr > mid) collect(p << 1 | 1, mid + 1, r, ql, qr, type); }

注意每次使用前要清空segNodes。不要边收集边加边，因为segNodes是全局数组，容易在递归中乱掉。简单做法是在每一种区间操作里先clear()，再collect()，最后统一遍历segNodes加边。

3.3 Dijkstra 主过程

Dijkstra 本身不需要针对线段树做任何特殊处理。虽然图里有很多虚拟内部节点，但它们只是普通节点，不影响正确性：

vector<ll> dist(tot + 1, INF); void dijkstra(int s) { priority_queue<P, vector<P>, greater<P>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { P top = pq.top(); pq.pop(); ll d = top.first; int u = top.second; if (d != dist[u]) continue; for (Edge &e : g[u]) { if (dist[e.to] > d + e.w) { dist[e.to] = d + e.w; pq.push({dist[e.to], e.to}); } } } }

一个建议：tot在跑 Dijkstra 前必须已经是最终值，所以dist的 vector 最好在读完所有边之后再创建，或者直接把dist定义成全局数组。如果提前用tot初始化，就要保证没有后续建图操作了。

3.4 完整参考实现

把上面几段拼起来，就是一个能用的版本：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> P; const int MAXN = 100000 + 5; const int MAXNODE = MAXN * 10; const ll INF = 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to; ll w; }; vector<Edge> g[MAXNODE]; int id[2][MAXN << 2]; int n, q, s; int tot; vector<int> segNodes; void addEdge(int u, int v, ll w) { g[u].push_back({v, w}); } void build(int p, int l, int r, int type) { if (l == r) { id[type][p] = l; return; } int mid = (l + r) >> 1; build(p << 1, l, mid, type); build(p << 1 | 1, mid + 1, r, type); id[type][p] = ++tot; if (type == 0) { addEdge(id[type][p], id[type][p << 1], 0); addEdge(id[type][p], id[type][p << 1 | 1], 0); } else { addEdge(id[type][p << 1], id[type][p], 0); addEdge(id[type][p << 1 | 1], id[type][p], 0); } } void collect(int p, int l, int r, int ql, int qr, int type) { if (ql <= l && r <= qr) { segNodes.push_back(id[type][p]); return; } int mid = (l + r) >> 1; if (ql <= mid) collect(p << 1, l, mid, ql, qr, type); if (qr > mid) collect(p << 1 | 1, mid + 1, r, ql, qr, type); } vector<ll> dist; void dijkstra(int s) { dist.assign(tot + 1, INF); priority_queue<P, vector<P>, greater<P>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { P top = pq.top(); pq.pop(); ll d = top.first; int u = top.second; if (d != dist[u]) continue; for (Edge &e : g[u]) { if (dist[e.to] > d + e.w) { dist[e.to] = d + e.w; pq.push({dist[e.to], e.to}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q >> s; tot = n; build(1, 1, n, 0); build(1, 1, n, 1); while (q--) { int op; cin >> op; if (op == 1) { int u, v; ll w; cin >> u >> v >> w; addEdge(u, v, w); } else if (op == 2) { int u, l, r; ll w; cin >> u >> l >> r >> w; segNodes.clear(); collect(1, 1, n, l, r, 0); for (int x : segNodes) addEdge(u, x, w); } else { int l, r, u; ll w; cin >> l >> r >> u >> w; segNodes.clear(); collect(1, 1, n, l, r, 1); for (int x : segNodes) addEdge(x, u, w); } } dijkstra(s); for (int i = 1; i <= n; i++) { if (i > 1) cout << ' '; cout << dist[i]; } cout << '\n'; return 0; }

这段代码我建议自己手写一遍。第一次写的时候很容易把 build 里的 type 写反，尤其是id[type][p]和子节点的对应关系。如果建错方向，样例往往会在很后面的步骤才算错。

4. 复杂度、空间和一种更省边的写法

4.1 点数和边数到底怎么估算

先看点。n 个原图节点，两棵线段树各自有 n-1 个内部节点，所以总节点数大约是：

n + 2 * (n - 1) = 3n - 2

也就是说 3n 级别。如果 n = 1e5，图节点只有 30 万左右，远小于很多人想象的 4n 或 8n。之所以要把数组开到 10 倍，主要是为了容错，以及防止某些递归索引比较极限的写法。

边数方面，每棵树内部有 n-1 个非叶子节点，每个非叶子节点有两条 0 权边，两棵树就是 4n 条内部边。每次区间操作最多拆出 2log n 个节点，所以新增边数大约是 O(log n)。因此总边数可以写成：

O(4n + q log n)

实际运行中 q = 1e5，log n 大约 17，总边数在百万级别，这对现代机器来说很轻松。

4.2 时间复杂度分析

Dijkstra 跑在约 3n 个点、O(n + q log n) 条边上，时间复杂度是：

O((n + q log n) log n)

前面的构建过程本身就是 O(q log n)。所以整体复杂度是完全可以接受的。需要注意的是一开始如果选择朴素建图，复杂度会变成 O(nq)，这就是为什么这个题必须用线段树优化。

4.3 用临时虚点减少高权边数量

上面代码在操作 2 中，把 u 到每个区间节点都直接加一条权值为 w 的边。如果要连的区间节点有 k 个，就会加 k 条 w 边。一个常见的替代方案是先新建一个临时虚点 tmp，然后从 u 向 tmp 加一条权值为 w 的边，再从 tmp 向那 k 个区间节点各连一条 0 权边。

// 操作 2 优化 int tmp = ++tot; addEdge(u, tmp, w); segNodes.clear(); collect(1, 1, n, l, r, 0); for (int x : segNodes) addEdge(tmp, x, 0);

操作 3 类似，只是方向反过来：

// 操作 3 优化 int tmp = ++tot; segNodes.clear(); collect(1, 1, n, l, r, 1); for (int x : segNodes) addEdge(x, tmp, 0); addEdge(tmp, u, w);

这样每条区间操作加的是 2log n + 2 条边，其中只有一条大权值 w 边，其余都是 0 权边。从边数上看可能只少了一部分，但 Dijkstra 在松弛时，面对的小权值 0 边更多，优先队列里的状态不会因为大量同权 w 边而变得混乱。代价是每次操作多了一个节点，总点数从 3n 变成 3n + q，仍然可控。

如果你不想折腾虚点，直接连边版本也能过。两种写法没有本质差别，取决于你是否想挤压常数。

5. 做题时最容易踩的坑

5.1 两棵树的父子方向建反

这是这个题最经典的错误。如果你把第一棵树建成了子向父连 0 权边，那么从点 u 连到区间节点后，没法向下走到叶子；反过来，区间向点 u 连边时，区间内点也没法向上汇聚到区间节点。结果就是样例输出和期望值差了一大截。

我的检查方式是：操作 2 是“点进区间”，先走到一个高处节点，再往低处叶子走，所以用父向子的树；操作 3 是“区间进点”，叶子要先往高处汇聚，所以用子向父的树。建树的时候，看到addEdge的方向，先问自己这条 0 权边能让谁走到谁。

5.2 叶子节点编号处理失误

叶子节点如果直接设置成原节点编号，就不需要额外加边。如果你非要在叶子处新建节点，那么两棵树各自的叶子节点需要和原节点连通。这里有一个很隐蔽的问题：你可能需要建两条方向相反的 0 权边，否则某些转移会漏掉。直接复用原节点编号是最省事也最不容易错的做法。

我在最初的版本里把叶子也++tot了，然后为了让它能参与所有转移，额外加了很多 0 权边，反而把自己绕晕了。后来改成叶子复用原编号，代码立刻清晰很多。

5.3 数组大小不够

虽然理论节点数约 3n，但如果你用临时虚点优化，或者线段树数组下标开得不够，会出现各种神秘的越界问题。建议id数组开到MAXN << 2，图节点数组开到MAXN * 10。不要吝啬这一点内存，线段树优化建图的坑基本都是越界造成的。

特别是递归建树时，线段树数组下标可能到达 4n 左右，因此id[2][MAXN << 2]中的MAXN << 2是必须的。如果你开成MAXN，很容易在 build 后半段直接访问到非法内存。

5.4 INF 和 long long

这个题边权可能非常大，累加后的最短路可能突破 int 上限。我见过有人用0x3f3f3f3f当 INF，然后答案在某个节点上一直是 INF，最后输出变成奇怪的大数。Dijkstra 的 dist、边权、优先队列里的 pair 都必须用 long long。

INF 我习惯开0x3f3f3f3f3f3f3f3fLL，既能防止溢出，又不会导致 dist + w 溢出。如果用1e18也可以，但不要用0x7f7f7f7f这种 int 级别的值。

5.5 优先队列里的过期状态

Dijkstra 里一定要写if (d != dist[u]) continue;或者if (d > dist[u]) continue;。由于我们加了很多 0 权边，同一个点可能被多次推入优先队列。如果少了这个判断，复杂度会退化，甚至出现死循环式的重复松弛。虽然理论上不会死循环，但效率会很难看。

另外，pair 的比较是按 first 再按 second。如果你把图节点编号作为 pair 第一维，就会变成按点编号排序，完全错误。正确写法是pair<ll, int>，第一维是距离，第二维是节点编号。

5.6 答案只输出前 n 个节点

最后输出时，必须只输出dist[1]到dist[n]。线段树内部节点也有 dist 值，但它们只是虚拟节点，不属于答案范围。如果你图省事直接遍历1..tot输出，会多出一堆奇怪的距离，看起来就像 bug 一样。

5.7 区间查询时 clear 的位置

segNodes是全局 vector，每次操作前必须clear()。如果放在 collect 函数内部 clear，递归会把上一层收集到的结果清掉，最后只留下最后一个区间的节点。我建议只在操作处理的入口处 clear，不要在 collect 内部做任何清空操作。

6. 这个技巧还能扩展到哪些地方

6.1 动态开点线段树优化建图

如果原图编号范围很大，比如 1e9，普通静态线段树无法直接开 4 倍数组。可以把线段树优化建图和动态开点结合起来，只在访问到某个区间时才创建节点。原理完全一样，只是把 id 数组换成了动态指针或哈希表。这类题往往配合离散化使用，思路依然是“区间拆成 O(log n) 个节点”。

6.2 树链剖分上的区间最短路

如果题目要求处理树上路径到某个点的连边，可以先对树做树链剖分，把一条路径拆成 O(log n) 个连续区间，再用线段树优化建图。这样就相当于支持了“路径 -> 区间”和“区间 -> 路径”的最短路建图。扩展性很强，但前提是先把普通区间版的线段树优化建图吃透。

6.3 有向图与无向图

CF 787D 里的区间边是单向的。如果题目要求双向区间边，比如 u 既可以进区间，区间内点也可以到 u，那么可以把操作 2 和操作 3 都各建一遍。两棵树仍然需要保留方向，不能图省事把内部 0 权边改成双向。因为双向边会让区间节点之间出现任意 0 权互达，破坏整个建图语义。

7. 关于这题的一点个人体会

线段树优化建图的名字听起来很唬人，实际拆开就是一个很朴素的思想：把大规模的区间转移，用少数代表节点承担。真正难的地方不是 Dijkstra，也不是线段树递归，而是搞清楚两棵树的角色和边的方向。我做这题的时候，第一版代码样例一直差一点，检查了半天才发现操作 2 和操作 3 用反了树。

后来我把“点进区间”和“区间进点”分别画成了两条 0 权链路：一条从上往下广播，一条从下往上汇聚。画完之后，整个图就清清楚楚了。如果你现在也被这题卡住，我建议先别急着看更多模板，拿小数据手动模拟一遍建图过程，把每个内部节点编号都写出来，再对照这一段路径去跑 Dijkstra。理解了那两条 0 权链，这个题就再也不会难倒你。