拼多多笔试复盘：离散化前缀和、DP 边界初始化与树链剖分

《面试题目》

1. 第二题：离散化 + 前缀和。
2. 第三题：一道 DP 优化题。
3. 第四题：树链剖分（长链剖分）题。
4. 第一题：难度较低的基础题（原文未展开）。

《参考解析》

离散化要连「+1」一起离散：做区间合并或前缀和时，如果按左端点做离散化，必须把每个区间的「右端点 +1」也放进候选集合，否则被区间覆盖的连续段会被拆错，最后一个覆盖点之后的那一段查不到。这类错误不会在样例上暴露，只能靠构造边界反例发现——写之前先把「坐标集合需要包含哪些点」列清楚，比写完再 debug 便宜得多。

DP 的边界初始化要和状态定义对齐：这题错在默认边界为无穷大。多维 DP 里第 0 行、第 0 列通常不是「不可达」，而是有具体的物理含义（例如前 j 个元素全选、只走横竖边的代价），写成无穷大之后所有依赖它的转移都被污染，表现为「样例过、部分数据错」。习惯做法是先把状态含义写成一句话，再逐个推 i=0 与 j=0 的取值。

取模场景下不能用 min 比大小：当权值取模后再比较，原始大小关系已经丢失，必须额外记录真实值或用 pair 比较；这篇帖子里最后一分钟才发现「谁小谁是儿子」的判断失效，正是这个问题。

考试策略上更值钱的两条：一是先拿暴力分再优化，第四题暴力拿到 16 分说明保底策略是有效的；二是复杂数据结构没有板子时不要硬写——40 分钟内手写长链剖分并 debug，期望收益远低于把前面题的对拍和边界检查做完。最后「少删一个括号导致编译不过」这种事，交卷前留 2 分钟本地编译一次就能避免。