题目分析

本题是 JOI 2014 的一道难题，要求在 $M+2$ 行 $N$ 列的网格上，通过选择性地放置装置，使得从顶部任意列下落的球最终都到达底部同一列，且总花费最小。

---

核心难点

1. $N$ 最大 $10^9$，无法枚举列。
2. $M$ 最大 $10^5$，需要低于 $O(M^2)$ 的算法。
3. 装置的作用是局部映射：如果球在第 $i+1$ 行落在 $[A_i, B_i]$ 内，就会被传送到 $C_i$ 列。

---

问题转化

将过程看作函数复合。设 $f_i: \{1,\dots,N\} \to \{1,\dots,N\}$ 表示经过第 $i+1$ 行（装置 $i$ 所在行）后的列变化：

• 不放置装置 $i$：$f_i(x) = x$（恒等映射）。
• 放置装置 $i$： $ f_i(x) = \begin{cases} C_i & \text{if } x \in [A_i, B_i] \\ x & \text{otherwise} \end{cases} $

整个系统的变换为： $ F(x) = (f_M \circ f_{M-1} \circ \cdots \circ f_1)(x) $ 目标是选择哪些 $i$ 放置装置，使得 $F(x)$ 是常数函数 $y$（对所有 $x$ 成立）。

---

倒推思路

从底部向上思考更直观。

最后一行（装置 $M$）：
球进入第 $M+1$ 行列 $x$，若 $F(x) = y$ 对所有 $x$ 成立，则 $f_M(x)$ 必须全部等于某个值 $t$，且从 $t$ 到底部时就是 $y$（最后一行无装置，所以 $t=y$）。
于是要求：对所有 $x$，$f_M(x) = y$。

分析放置装置 $M$ 的情况：

• 若 $x \in [A_M, B_M]$，则 $f_M(x) = C_M$，所以必须 $C_M = y$。
• 若 $x \notin [A_M, B_M]$，则 $f_M(x) = x$，所以必须 $x = y$。

第二点意味着：不在区间 $[A_M, B_M]$ 内的 $x$ 只能是 $y$ 这一个值。因此 $[A_M, B_M]$ 必须覆盖除了 $y$ 之外的所有列。
但如果 $y$ 在区间外，则 $C_M$（在区间内）不能等于 $y$，与 $C_M = y$ 矛盾。
所以 $y$ 必须在区间内，且区间外无元素，即： $[A_M, B_M] = [1, N]$ 并且 $C_M = y$。

结论：装置 $M$ 必须放置，且必须 $A_M=1$，$B_M=N$，$C_M = y$。

---

继续倒推

假设从第 $i+1$ 行开始，所有进入列最终都要到达 $y$。
设此时进入列为 $x$，经过装置 $i$ 后变为 $f_i(x)$，然后进入下一行递归。

要求对所有 $x$，$f_i(x)$ 最终映射到 $y$。
即：$f_i(x)$ 必须等于某个 $t$，使得从 $t$ 开始后续过程能到 $y$。

同样分析装置 $i$ 若放置：

• $x \in [A_i, B_i]$ 时，$f_i(x) = C_i$，所以必须 $C_i = t$ 且 $t$ 最终到 $y$。
• $x \notin [A_i, B_i]$ 时，$f_i(x) = x$，所以必须 $x = t$。

因此，不在区间内的 $x$ 只能是 $t$ 这一个值。所以 $[A_i, B_i]$ 必须覆盖除了 $t$ 之外的所有列。
若 $t$ 在区间外，则 $C_i$（在区间内）不能等于 $t$，矛盾。
所以 $t$ 必须在区间内，且区间外无元素，即： $[A_i, B_i] = [1, N]$ 并且 $C_i = t$，且 $t$ 最终到 $y$。

这意味着：如果放置装置 $i$，它必须覆盖整行，且它的 $C_i$ 值必须与下一行期望的“入口列”相同。

---

关键推论

由上述推导可得：

• 若在某一行放置装置，则该装置必须覆盖整行（$A_i=1, B_i=N$）。
• 所有被放置装置的 $C_i$ 必须相同，记为 $y$。
• 这些装置必须连续放置，从某一行 $s$ 开始到 $M$ 结束。
• 在 $s$ 行之前不能有装置（否则不满足覆盖整行条件）。

但这样一来，从第 $1$ 行到第 $s$ 行没有装置，球会保持初始列 $x_0$ 不变，到达第 $s$ 行时列是 $x_0$。
为了使 $x_0$ 经过装置 $s$ 后变成 $y$，我们需要对所有可能的 $x_0$ 都有 $x_0 = y$ 或在 $[A_s,B_s]$ 内且 $C_s=y$。
由于 $[A_s,B_s]=[1,N]$，所以只要 $C_s=y$，无论 $x_0$ 是什么，经过装置 $s$ 后都变成 $y$。

所以可行方案是：
选择某个 $y$，并选择一个连续的行区间 $[s, M]$，使得对其中每个装置 $i$ 都有 $A_i=1, B_i=N, C_i=y$，然后放置这些装置。总花费就是这些 $D_i$ 的和。

---

与样例的冲突

但是，样例 1 中放置了装置 2、4、5，其中装置 2 的区间是 $[1,2]$，不是 $[1,6]$，不符合“必须覆盖整行”的推论。
这说明上述推导有误——我们错误地假设了“要使所有 $x$ 映射到同一个值，区间必须覆盖整行”。其实并不需要。

---

修正思路：允许部分覆盖

正确思路：
不要求 $f_i(x)$ 本身是常数，而是要求 $f_i(x)$ 经过后续步骤后能到达同一个 $y$。
这意味着 $f_i(x)$ 可以不同，只要它们最终都能到 $y$。

这样，装置 $i$ 放置时，会将区间 $[A_i, B_i]$ 内的所有列映射到 $C_i$，区间外的列保持不变。
为了让所有列最终到 $y$，需要满足：

1. 区间内的列：$C_i$ 最终能到 $y$。
2. 区间外的列：它们本身（即 $x$）最终能到 $y$。

于是，问题转化为：从底部向上，维护“哪些列最终能到达 $y$”的集合，然后判断能否让所有列最终到 $y$。

---

图论建模（正解框架）

考虑每个列 $x$ 作为一个节点。
放置装置 $i$ 表示：将区间 $[A_i, B_i]$ 的所有节点用一条有向边连接到节点 $C_i$，花费 $D_i$。
不放置装置 $i$ 表示：每个节点 $x$ 到 $x$ 的边（花费 0）。

目标：选择一些装置（即一些边集），使得从任意节点 $x$ 出发，沿着选择的边行走，最终都到达同一个节点 $y$。
注意：因为装置是按顺序作用的，这个行走方向是正向（从上到下）。

等价于：选择一个 $y$，对于所有 $x$，存在一条从 $x$ 到 $y$ 的路径（使用某些装置边），且总花费最小（花费是所选边的费用之和，但一条边被多条路径共享时只计一次费用）。

---

这可以转化为：从 $y$ 反向建图，用 Dijkstra 求从 $y$ 到所有节点的最短路，但这里边的费用是在选择装置时一次性支付的，所以需要设计合适的状态转移。

最终做法是：

• 定义 $dp[i][v]$ 表示从第 $i+1$ 行开始，所有列最终要到达 $v$ 的最小花费。
• 从 $i=M$ 倒推到 $i=1$。
• 转移时考虑装置 $i$ 是否放置，放置时会将一个区间的列映射到 $C_i$，然后要求 $C_i$ 和区间外列最终都到 $v$。
• 用线段树优化区间取最小值的操作。

---

复杂度

使用线段树优化 Dijkstra 式的 DP 转移，总复杂度 $O(M \log N)$，可处理 $M=10^5$ 且 $N$ 很大的情况。

---

总结

本题的核心是将装置映射转化为图论问题，通过最短路和区间数据结构优化求解。关键突破点是放弃“每行必须覆盖整行”的错误推论，采用“允许部分覆盖，但要求所有列最终汇于一点”的思路，从而得到可行的算法框架。