「美团 CodeM 复赛」通信 题解

题目回顾

• 有 $N$ 个信号塔，第 $i$ 个塔的位置是 $i$，信号强度 $X_i$（互不相同）。
• 有 $N$ 个人，第 $i$ 个人的位置是 $i$，向左走一格要 $A$ 秒，向右走一格要 $B$ 秒。
• 传递规则：当 $i$ 有信息时，选择 $j$（$1 \le j \le i$），令 $k = \arg\max_{j \le t \le i} X_t$，然后 $i$ 和 $j$ 同时向 $k$ 移动，都到达 $k$ 后信息从 $i$ 传给 $j$，两人瞬间回到原位置，$i$ 失去信息，$j$ 获得信息。
• 对每个 $i$ 求信息传到 $1$ 的最短时间 $f_i$ 及方案数 $g_i$（模 $2^{32}$）。
• $f_1=0,\ g_1=1$。
• 输出 $\oplus f_i$ 和 $\oplus g_i$（分别用 64 位有符号、32 位无符号类型计算异或）。

---

一、数学模型化简

1. 确定 $k$

由于 $X$ 互不相同，设 $L(i)$ 为 $i$ 左边第一个满足 $X_{L(i)} > X_i$ 的位置（若不存在则 $L(i) = -1$，但方便起见可以设 $L(1)=0$ 并特判）。
对任意 $j \in [1,i]$：

• 如果 $j \le L(i)$，则区间 $[j,i]$ 的最大值位置 $k = L(i)$（因为 $X_{L(i)} > X_i$ 且 $L(i)$ 左边没有更大的跨过它）。
• 如果 $j > L(i)$，则 $k = i$（$X_i$ 是 $[j,i]$ 的最大值）。

2. 传递时间

记 $m = k$。

情况 A：$m = i$（$j > L(i)$）

• $i$ 到 $m$：距离 $0$，时间 $0$。
• $j$ 到 $m$：$j$ 在 $i$ 左边，向右走 $i-j$ 格，每格 $B$ 秒，时间 $B(i-j)$。
• 总时间 $T(i,j) = \max(0, B(i-j)) = B(i-j)$。

情况 B：$m = L(i)$（$j \le L(i)$）

• $i$ 到 $m$：向左走 $i - L(i)$ 格，每格 $A$ 秒，时间 $A(i - L(i))$。
• $j$ 到 $m$：向右走 $L(i) - j$ 格，每格 $B$ 秒，时间 $B(L(i)-j)$。
• 总时间 $T(i,j) = \max\big(A(i - L(i)),\ B(L(i)-j)\big)$。

---

二、动态规划方程

设 $f_i$ 为从 $i$ 传到 $1$ 的最短时间，显然 $f_1=0$。

一次传递：从 $i$ 传到 $j$ 花费 $T(i,j)$，然后从 $j$ 传到 $1$ 花费 $f_j$。
所以：

$$f_i = \min_{1 \le j < i} \big[ f_j + T(i,j) \big]. $$

代入 $T(i,j)$ 的分情况：

1. $j > L(i)$：$f_j + B(i-j) = f_j - Bj + Bi$。 令 $h_j = f_j - B \cdot j$，则这部分最小值 = $B \cdot i + \min_{j > L(i)} h_j$。

2. $j \le L(i)$：$f_j + \max\big(A(i-L(i)),\ B(L(i)-j)\big)$。
   令 $C = A(i-L(i))$，则

   • 若 $B(L(i)-j) \le C \iff j \ge L(i) - \frac{C}{B}$，则时间 = $f_j + C$。
   • 若 $j < L(i) - \frac{C}{B}$，则时间 = $f_j + B(L(i)-j) = f_j + B L(i) - B j$。

所以这部分要分两段求最小值。

---

三、数据结构设计

观察：

• 对 $j > L(i)$ 的部分，需要支持区间 $\min\{h_j\}$。
• 对 $j \le L(i)$ 的部分，需要支持：
  • 区间 $[L(i)- \lfloor C/B \rfloor, L(i)]$ 求 $\min\{f_j\}$（当 $C$ 较大时）。
  • 区间 $[1, L(i)- \lfloor C/B \rfloor - 1]$ 求 $\min\{f_j - B j\}$（再加 $B L(i)$）。

但 $C/B$ 可能不是整数，且分界点会随 $i$ 变化。

---

代码中的简化技巧

在给定代码中，使用了线段树维护两个值：

• min_value[0]：存 $f_j - B j$（用于 $j > L(i)$ 的情况，但实际处理时是另一形式）。
• min_value[1]：存 $f_j + B L(i) - B j$？
  不，从代码 awp.min_value[1] = dp[i] - 1LL * i * a 看，这里 $a$ 就是 $A$，所以它存的是 $f_j - A j$？可能用于另一种对称情况。

实际上，因为 $T(i,j)$ 的表达式是对称的，可以用单调栈维护 $L(i)$，并在栈变化时更新线段树的“偏移量”（delta），使得查询能在 $O(\log N)$ 完成。

---

四、代码核心流程

1. 读入 $N, A, B, X[1 \dots N]$。
2. 单调栈求 $L(i)$（左侧第一个 $X$ 更大的位置）。
3. 线段树 tree 维护两个值：
   • tree[id].min_value[0]：对应 $f_j - B j$（或者带偏移后的值）。
   • tree[id].min_value[1]：对应 $f_j - A j$（或者带偏移后的值）。 以及对应的方案数 cont[0] 和 cont[1]。
4. 遍历 $i = 1 \dots N$：
   • 更新栈，并在栈弹出时更新线段树区间（update 操作，增减偏移量）。
   • 查询（query 函数）得到两个候选最小值和方案数，合并得到 $f_i, g_i$。
   • 将 $i$ 的信息插入线段树。
5. 输出 $f_1 \oplus \dots \oplus f_N$ 和 $g_1 \oplus \dots \oplus g_N$。

---

五、时间复杂度

• 单调栈操作总 $O(N)$。
• 线段树每次更新或查询 $O(\log N)$。
• 总复杂度 $O(N \log N)$，可过 $N \le 10^6$（常数较小）。

---

六、关键点总结

1. 分类讨论 $j$ 与 $L(i)$ 的位置关系，将 $T(i,j)$ 化简为较简单的形式。
2. 将 $\max$ 表达式拆为分段函数，分别对应不同的 $j$ 范围。
3. 用单调栈维护 $L(i)$，并借助线段树动态维护两类最小值查询，支持区间加偏移量。
4. 方案数在求最小值时同时累加（模 $2^{32}$）。
5. 最终答案用异或输出。

---

示例对应（样例）：

$$\begin{cases} f_1 = 0 & g_1 = 1 \\ f_2 = 3 & g_2 = 1 \\ f_3 = 13 & g_3 = 1 \\ f_4 = 9 & g_4 = 2 \\ f_5 = 12 & g_5 = 4 \\ f_6 = 13 & g_6 = 1 \end{cases} $$

输出：

6
6