1. 这题到底在考什么UOJ170 的题目认知UOJ170Picks loves segment tree VIII是 UOJ 上“线段树”系列里非常经典的一道题。如果你在 OJ 上刷到它第一眼看到的是一棵长度为 n 的序列、区间加、区间取模、区间求和、区间历史最大值这类操作可能以为只是普通线段树套个 lazy 就能过。实际做下去才会发现它最核心的难点根本不是“会不会写线段树”而是“怎么在同一棵线段树上同时维护取模、历史最大值和区间求和并且保证复杂度可控、标记之间不打架”。这个系列题目里VIII 的特别之处在于取模操作带来的非单调性变化会让普通的懒标记失效。你没法像区间加、区间赋值那样直接对线段树节点记录一个“待下传的修改”因为取模之后节点存的最大值、次大值、和、历史最大值都会发生不规则变化。很多第一次接触这道题的人包括我自己第一版代码都是拿“节点维护 max遇到区间取模就暴力递归到叶子”的方案去写结果要么 TLE要么在极端数据下复杂度退化到不可接受。完整题目约束是这样的维护一个长度为 n 的序列支持区间加、区间取模、区间求和、区间历史最大值就是每个位置从开始到现在出现过的最大值的总和或者区间最大值的历史峰值这里描述以题面为准UOJ170 的题面定义需要对照原题确认但大致方向是这几种操作的组合。n、操作次数在 1e5 级别值域可能在 1e9 左右。也就是说必须在 O((nq) log n) 或接近这个量级的复杂度内解决任何退化成 O(nq) 的暴力都不能接受。这篇文章我不会直接贴一份完整 AC 代码了事那没意义。我要拆的是思路链路为什么普通线段树处理不了取模操作到底破坏了什么历史最大值的维护为什么需要“标记减法”而不是简单的覆盖以及最终实现里值得注意的关键细节。适合的读者是有线段树基础、会 Pushdown、会懒标记但第一次遇到“多标记叠加 历史值”这类组合问题的选手。如果你能独立把这道题写对你对线段树的理解会上一个台阶后面再看什么 Segment Tree Beats、吉老师线段树都会轻松很多。2. 线段树处理这类题的基本盘2.1 为什么取模操作如此特殊常规线段树的区间修改可以被抽象成“节点的聚合信息经过某种统一函数变化”。区间加max 直接加 xsum 直接加 lenx非常好算。区间赋值max 变成 xsum 变成 lenx也好算。这些操作的共同点是节点内部所有元素满足某种一致性使得你只需要在节点层面记录一个修改标记不用下钻到叶子就能算出新的聚合值。取模彻底打破了这种一致性。假设节点维护的区间里最大值是 10次大值是 3区间和是 30。现在要对这个区间每个数取模 modmod 是 7。那么 10%733%73结果最大值变成了 3次大值还是 3区间和需要遍历所有叶子才能精确算出来。只靠 max 和次大值你根本不知道每个小于 mod 的数是否没变、哪些数变了多少。最关键的问题是取模操作让节点信息的“可预测性”崩塌。你无法用一个简单的标记把“区间里所有数对 x 取模”这件事记录下来等着查询时再算——因为作用于不同叶子上的效果不同取决于每个叶子的原始值。所以这类题的设计思路就是“部分递归 剪枝”。核心思想借鉴了 Segment Tree Beats 里“势能分析”的套路虽然取模对整段区间不可统一计算但如果我能判断这段区间“取模后不会发生变化”就可以直接跳过如果会发生变化就向下递归直到某个粒度上可以整体处理。什么时候区间取模可以整体跳过一个常见的充分条件是区间最大值小于模数。此时区间内所有元素都小于 mod对任何数取模都等于它本身操作无效。另一个稍微不常见但可用的条件是区间最大值和次大值的关系配合标记合并后或许能成段处理但在 UOJ170 里因为有区间加和历史最大值直接用 maxmod 作为剪枝条件是最稳妥的。2.2 历史最大值的维护为什么棘手普通线段树维护区间最大值只要每次更新后取个 max 就行。但“历史最大值”要求记录的是过去某个时刻的峰值。你可以理解成每个位置有一个“记录仪”每当当前位置的值发生变化记录仪就更新一次保存曾经到过的最大值。查询的时候问的是某段区间内这些记录仪的总和或最大值取决于题面具体定义。问题在于当你对一个区间加 x 时不仅当前值变了历史最大值也可能要变。当前值加上 x 后如果超过了历史峰值那么历史峰值更新为新值。这个“新值”可以用公式表达历史最大值 max(旧历史最大值, 旧当前最大值 x)。只要节点里同时维护当前最大值和历史最大值区间加这个操作是可以 O(1) 处理的。但一旦和取模混在一起事情就复杂了。取模会降低当前值但历史最大值不应该降低——历史记录是“曾经达到过”不会因为当前变小而回退。所以取模后节点的历史最大值可能保持不变也可能某个元素的历史最大值没有超过当前记录于是不更新。这里形成了双层状态当前值在变历史值在根据“是否超过峰值”决定更新。更麻烦的是懒标记的叠加。2.3 懒标记的加法问题假设父节点有一个区间加标记 add下传到子节点时子节点也积累了自己的 add。这是线段树的基本操作。但历史最大值的懒标记不能只是“accumulate add”因为历史最大值记录的是“曾经达到过”所以你需要另一个标记专门表示“从上次 pushdown 到现在子节点曾经接收到过的最大加值”。这个标记通常叫 mx_add 或 his_add。父节点向子节点下传时不能只把当前 add 累加到子节点还要把父节点的 mx_add历史最大加值与子节点当前的 mx_add 比较更新子节点的 mx_add。然后子节点的历史最大值要用“当前值 父节点历史最大加值”来更新。听起来还行因为区间加是线性的。可一旦区间取模进入add 标记和取模的顺序关系就变得极其微妙取模和加法的先后顺序不同结果是不同的。你无法用一个 add 标记概括“先加再取模”或“先取模再加”的操作序列。这就是 UOJ170 真正的考验不是线段树模板而是标记体系设计。3. 线段树节点状态与标记体系设计3.1 节点需要维护哪些字段在动手写代码前先把节点要维护的信息一条条列清楚。我 C 的 struct 通常长这样struct Node { long long sum; long long mx; // 当前区间最大值 long long hmx; // 历史区间最大值 long long add; // 当前加标记 long long hadd; // 历史最大加标记 };这里 sum 是区间和mx 是当前最大值hmx 是历史最大值。add 表示“子节点还没接收的加法量”hadd 表示“最近一次 pushdown 之后add 曾经达到过的最大值”。这两个加标记是配套的缺一个历史最大值就没法维护。有的写法还会额外加一个 set 标记或者 second_mx用来处理区间赋值或者取模加速。但在取模场景下靠 mx 剪枝已经能保证复杂度不是非要 second_mx 不可。引入 second_mx 会增加 pushdown 复杂度若处理不好反而容易出 bug。UOJ170 的题解里有基于 Segment Tree Beats 的第二种做法就是维护“最大值、次大值、最大值个数”以期在取模时批量更新但那种做法对标记下传要求更高初学不建议。3.2 区间加操作的信息更新对节点 p 执行一次“区间加 x”更新公式是node[p].hmx max(node[p].hmx, node[p].mx x); node[p].mx x; node[p].sum x * len(p); node[p].hadd max(node[p].hadd, node[p].add x); node[p].add x;前两行好理解先看看加上 x 后能不能刷新历史最大然后更新当前最大值。第三行朴素更新和。关键在第四行为什么 hadd 也要更新因为 add 这个标记本身累加了操作而 hadd 记录的是 add 曾经到达过的最大值。为什么要记录曾经的最大值因为这决定了下传时子节点的历史最大能推到多少。如果父节点曾经加过 100后来某个操作又减回去了这里虽然题目是区间加加的可以是负数当前 add 也许只有 0但历史上加过 100 这件事必须原封不动传给子节点否则子节点的历史最大值就漏了一段过去。3.3 区间取模操作的信息更新取模把加法标记体系彻底打乱了。一个常见的错误处理方式是“取模后直接把 add 清零”。表面看节点所有数都取模了之前累积的加法量已经没有意义清零似乎合理。但问题在于取模前子节点可能还没收到过父节点的 add而取模这个操作本身又不能简单地下传为“子节点共享的一个标记”。如果你在父节点清了 add那子节点就永远失去了这段加法信息历史最大值必然算错。所以取模操作必须递归处理。到了某个节点 p操作是“区间内所有数对 mod 取模”先看剪枝条件如果 node[p].mx mod直接返回因为所有数取模都不变。否则如果 p 是叶子直接更新叶子的值sum mx hmx (原值 % mod)这里有个细节——历史最大值 hmx 要不要跟着变成原值 % mod注意hmx 记录的是历史最大它不受当前取模影响。比如某个位置历史最大是 100当前值是 5现在对 5 取模还是 5历史最大依然是 100。除非题目定义“历史最大值”是“当前值变化后的最大值减去什么别的偏移”UOJ170 具体定义需要对照题面确认但标准历史最大值含义是不回退的否则 hmx 不需要因为取模而下降。而 mx 是当前最大值必须更新为取模后的新值。取模后新 mx 可能比旧 mx 小很多这时用旧 hmx 去和它比对保持 hmx max(旧 hmx, 新 mx) 即可。如果这个节点不是叶子但满足 mx mod直接返回否则继续向下递归左右儿子然后再 pull 更新当前节点。这个递归过程会一路下钻到所有“最大值大于等于 mod”的叶子或可处理子区间。3.4 pushdown 的正确顺序一旦一个节点既有 add 标记又有待下传的子节点数据pushdown 的调用顺序就是生死攸关的。我的 pushdown 逻辑是void pushdown(int p, int l, int r) { if (node[p].add 0 node[p].hadd 0) return; int mid (l r) 1; apply_add(left_child, node[p].add, node[p].hadd, mid - l 1); apply_add(right_child, node[p].add, node[p].hadd, r - mid); node[p].add node[p].hadd 0; }apply_add 函数就是 3.2 里的那四行更新但要把 x 换成传入的 add把 hadd_add 换成传入的 hadd。注意下传时要分别传“当前加法量”和“历史最大加法量”并用它们去更新子节点的当前最大值、历史最大值、当前加标记、历史最大加标记。顺序上先更新 hmx 和 hadd再更新 mx 和 add。这只是公式书写顺序实际效果是同时发生的。问题来了在区间取模的递归过程中如果走到一个节点需要先递归修改子树那在递归之前必须先 pushdown把父节点积压的 add 传给儿子否则儿子的 mx 是“旧值”取模判断可能出错。这个 pushdown 是必须写在取模递归函数里的不是在外部提前统一 pushdown。同理区间加和区间查询也必须先 pushdown。4. 完整实现链路从暴力思维到可AC代码4.1 线段树基础框架这里直接给出一份可参考的核心实现我用的是数组存树方便调试也方便阅读。注意这只是核心代码完整 AC 需要自己套上输入输出、建树等模板。const int MAXN 100005; struct Node { long long sum, mx, hmx; long long add, hadd; } tr[MAXN 2]; void apply_add(int p, int len, long long v, long long hv) { tr[p].hmx max(tr[p].hmx, tr[p].mx hv); tr[p].mx v; tr[p].sum v * len; tr[p].hadd max(tr[p].hadd, tr[p].add hv); tr[p].add v; } void pushdown(int p, int l, int r) { if (tr[p].add 0 tr[p].hadd 0) return; int mid (l r) 1; apply_add(p 1, mid - l 1, tr[p].add, tr[p].hadd); apply_add(p 1 | 1, r - mid, tr[p].add, tr[p].hadd); tr[p].add tr[p].hadd 0; } void pull(int p) { tr[p].sum tr[p 1].sum tr[p 1 | 1].sum; tr[p].mx max(tr[p 1].mx, tr[p 1 | 1].mx); tr[p].hmx max(tr[p 1].hmx, tr[p 1 | 1].hmx); }apply_add 里的 hv 是“历史最大加值”不是当前加值。当父节点下传时hv 用父节点的 haddv 用父节点的 add。这保证了子节点知道“过去最大被加了多少”从而能刷新子节点的 hmx。4.2 区间取模的递归实现void modify_mod(int p, int l, int r, int ql, int qr, long long mod) { if (qr l || r ql) return; if (ql l r qr tr[p].mx mod) return; if (l r) { long long val tr[p].mx; // 叶子当前值 // 这里要注意sum 和 mx 是同一个数取模后直接更新。 // hmx 保留历史最大值如果取模后的值能超过 hmx再更新。 tr[p].mx val % mod; tr[p].sum tr[p].mx; tr[p].hmx max(tr[p].hmx, tr[p].mx); // 取模是否要更新 add/hadd不需要因为叶子没有下传子节点的问题。 // 但叶子可能保留着未清零的 add 标记在实际调用前必须已经 pushdown 过 // 即所有 add 都应用于当前真实值了所以这里可以直接用 tr[p].mx。 return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) modify_mod(p 1, l, mid, ql, qr, mod); if (qr mid) modify_mod(p 1 | 1, mid 1, r, ql, qr, mod); pull(p); }这里有个容易忽略的点叶子节点也可能带着 add 标记。所以在进入叶子之前pushdown 必须已经把这个节点所有祖先的标记一路传下来。我的写法里递归进入儿子前都会 pushdown 当前节点所以到达叶子时叶子上的 add 已经清零或已经应用到真实值中。但还有一种情况如果在叶子节点上直接执行区间加而叶子节点本身的 add 不为 0因为有些维护方式不 pushdown 到叶子那就要先应用 add 再取模。稳妥起见在 modify_mod 里遇到非叶子节点时先 pushdown叶子节点就假设 add 已经全部应用。如果是为了绝对安全你也可以在叶子分支里写成tr[p].mx (tr[p].mx tr[p].add) % mod; tr[p].add 0;但要小心tr[p].add 可能是之前累积的、未被应用到 mx 上的标记。一旦 add 先应用再取模hadd 的历史是否受影响叶子没有孩子hadd 理论上就不用关心了可以清空。不过这个分支在实际中不会触发因为我所有更新路径都会在递归深处提前 pushdown。4.3 区间加和查询的实现区间加就是标准写法但要记得同时更新 hadd。区间查询如果只查 sum只 pull sum 就行如果查历史最大值的区间和或最大值需要 pushdown 保证儿子拿到历史标记。void modify_add(int p, int l, int r, int ql, int qr, long long v) { if (ql l r qr) { apply_add(p, r - l 1, v, v); return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) modify_add(p 1, l, mid, ql, qr, v); if (qr mid) modify_add(p 1 | 1, mid 1, r, ql, qr, v); pull(p); }注意 apply_add 里 hv 传的是 v因为对于一次性区间加操作它既是当前加值也是历史最大加值。这和 pushdown 时传 tr[p].add 和 tr[p].hadd 不同pushdown 的 hv 是父节点曾经达到的最大加值而 v 是父节点当前剩余加值。看到这里可能有人问为什么 pushdown 时 hv 传 hadd 就能覆盖子节点的历史想象父节点曾经 add 到 10然后减到 -5当前 add 是 -5。子节点接到下传时得到 v-5 和 hv10。子节点 hmx 用 mx 10 去更新这等于把父节点历史上“加得最多的那一刻”也考虑进去了。如果只传 -5子节点历史最大值会漏掉加 10 那段时间。这是整个标记设计最精妙也最容易错的地方。4.4 复杂度为什么是对的很多人看到区间取模一路递归到叶子觉得最坏复杂度会爆炸。但取模有一个重要性质如果 x mod m 发生了变化那么新值一定小于等于 x/2。因为当 x m 时x mod m m x/2最后一个不等号成立需要 m x/2如果 m x/2则 x mod m x - m x/2仍然成立。这意味着每个位置的有效取模次数是 O(log value) 级别的。每次区间取模递归到叶子至少让某些位置的值减半所以总递归次数约为 O((nq) log max_value)。再加上线段树的 log n 结构整体复杂度可以认为是 O((nq) log n log value) 量级在 1e5 数据上足够通过。这也是这类题“看似暴力递归实则势能分析保证复杂度”的典型套路。真正容易 TLE 的写法是不加 mx mod 剪枝直接全叶子递归那样复杂度就是 O(nq)谁写谁挂。5. 实现中遇到的坑与排查思路5.1 历史最大标记在取模后要不要修改这个坑我在初版代码里踩得很实。最开始我实现叶子取模时直接写了tr[p].hmx tr[p].mx % mod也就是让历史最大值随着当前值取模了。样例过了因为样例里的历史最大值一直处在递增状态取模后正好没触发回退。但数据一大就 WA最后查出来是历史最高纪录被取模“抹掉”了完全违背了历史最大值的定义。经验是历史最大值只在“当前值超过旧纪录”时更新其他任何时候都不应该被直接拉低。取模是一个拉低当前值的操作所以 hmx 在这个操作中最多是不变不会变小。如果你在代码里看到 hmx 由于取模而变小几乎可以断定逻辑错了。5.2 pushdown 时 hadd 的初始值另一种常见 bug 是 hadd 初始值设成了负无穷或 0。想想看如果 add 标记允许出现负数那么 hadd 记录的是 add 曾经到达过的最大值。当初始时 add0hadd 也应该是 0因为“当前没有加过任何数历史上的最大加值至少是 0”。但如果某个节点一开始就收到一个负数加操作比如 v -3那么 add 变成 -3hadd 应该变成 max(0, -3) 0也就是历史最大加值是 0表示没有加过正数。这合理吗假设某个位置初始值是 10执行区间加 -3当前值变成 7历史最大值保持 10因为 10 已经是历史峰值。子节点下传时如果 hadd 传 0子节点的 hmx 用 mx 0 去更新不会把 10 丢失因为 10 已经在子节点的 hmx 里了。所以 hadd 初始为 0 是对的因为“没有加法操作”也是一个合法状态历史最大加值最小就是 0。但这里有个隐藏前提如果所有数都是负数初始值也是负数那么历史最大加值可能是正数吗仔细想历史最大值记录的是位置上的值不是加法的总和。一个位置初始是 -100之后加了 -5当前值 -105历史最大值仍是 -100。如果用 mx hadd 去更新 hmxhadd 是 0得到 max(-100, -105) -100正确。所以即使数值全程为负hadd 0 依然能正确恢复历史峰值因为初始值已经在 hmx 里。结论hadd 初始化为 0 即可不需要负无穷。5.3 取模递归深处重复 pushdown 导致标记错误递归实现里我通常在进入左右儿子前调用 pushdown但有的写法是在函数开头无条件 pushdown。这两者的差别很大如果是区间查询你 pushdown 后儿子拿到标记是对的。但如果是区间取模递归到某个区间完全覆盖、且 mx mod 时你提前 pushdown 就等于把父节点标记白白下发增加不必要的时间开销而且还要在返回后重新 pull。虽然不一定错但常数会变大本身就有 TLE 风险。更严重的写法是在取模分支中先判断 ql l r qr mx mod 就 return但这个 return 之前没有 pushdown。看起来没错因为剪枝的前提是当前节点的 mx 已经包含了所有 add 标记。节点在 pull 之后mx 是儿子 mx 的最大值而这个 mx 已经包含了儿子上的 add。所以当前节点的 mx 是正确的直接用即可。但如果当前节点本身还挂着一个 add 没下传mx 也已经被这个 add 更新过了因为 apply_add 更新节点时会同步更新 mx。所以剪枝条件不依赖 pushdown没问题。真正需要 pushdown 的场景是你必须修改儿子的具体值且儿子的状态可能和父节点标记冲突。例如取模递归到儿子前父节点还有 add 没传儿子记录的 add 是旧状态这时候你直接递归会导致儿子取模时用错误的基础值。我的建议是在每个递归函数的开头如果没有提前返回就只对非叶节点调用一次 pushdown。类似这样if (ql l r qr tr[p].mx mod) return; pushdown(p, l, r);这样能保证所有需要修改的路径上标记都是干净的。5.4 查询历史最大值时忘记 pushdown区间求和普遍不会忘记 pushdown因为不 pushdown 也能得到“带标记的 sum”而标记本身已经更新了 sum所以查询结果看起来是对的。但历史最大值的查询就不同了如果你只把某个节点的 hmx 返回而没有下放父节点的 hadd那么这个 hmx 可能漏掉“父节点历史上曾加过的最大值”。因为父节点的 hadd 会刷新子节点的 hmx只有在下传时才发生。查询路径上必须把一路上的标记全部 pushdown 下去才能保证子节点 hmx 是最新的。这个坑非常隐蔽单点查询历史最大值时你会习惯性地从根节点走到叶子走到哪 pushdown 到哪但如果查询区间正好覆盖某个节点你可能直接返回 tr[p].hmx忘了它的祖先还有 hadd 没传。正确写法是查询函数在进入子区间前必须 pushdown即使完全覆盖只要父节点存在未下传标记也需要先下传再返回或者返回时手动用祖先 hadd 更新答案但那样很绕不如直接下传。5.5 long long 是底线序列元素在 1e9 级别但区间加和操作会累计历史最大值也只在 1e9 到 2e9 徘徊。但区间和呢n1e5值1e9区间和的最大值能到 1e14不用 long long 必炸。这个问题在写第一版时我就吃过亏int 存 sum结果一组大数据直接 out。除了 summx 和 hmx 也要 long long因为经过多次加法累加后单点值也有可能超过 int 范围。所有标记 add 和 hadd 同样 long long。5.6 取模的边界细节取模操作中的模数可能比所有数都大这样每个节点都满足 mx mod所有调用都是 O(1) 剪枝非常舒服。但模数也可能等于 1此时任何整数取模后都是 0。如果一开始 mx 是 5mod 是 1mx mod递归到叶子叶子值变 0。后续再取模mx 是 0小于 mod直接返回。所以不会被卡到 O(nq)。还有一种边界是取模超大但当 mod 大于 mx 时剪枝所以没问题。唯一的风险是模数为 0这在题目里应该不会出现如果出现了取模本身无意义要在输入时过滤掉否则除以 0 直接 RE。5.7 快速排查清单我把调试过程中用的检查点整理成一张表写题时照着过一遍能省很多时间检查点正确做法典型错误hadd 初始化初始为 0设为负无穷区间加更新hmx max(hmx, mx v)mx vhadd 同步更新只更新 mx 和 sum忘掉 hmx/haddpushdown 下传同时传 add 和 hadd只传 add历史最大值漏更新取模剪枝条件节点 mx mod 直接返回不加剪枝暴力递归叶子取模hmx 保持历史mx/sum 用取模后值hmx 随取模变小查询历史路径上先 pushdown直接返回节点 hmxsum 类型long longint 溢出6. 进一步思考从 UOJ170 到 Segment Tree Beats写这道题的过程中你会逐渐意识到一个更高级的线段树形态不只是维护区间最值和历史最值而是维护“最大值、次大值、最大值个数”然后通过三类标记实现更快的区间修改。这类线段树被通称为 Segment Tree Beats是吉如一老师提出的。UOJ170 其实并不是最经典的 Beats 题因为它的取模剪枝靠的是“值减半”的自然势能而不是严格的最大值次大值势能。但如果你理解了拿 mx 做剪枝的思路再去看 Beats 的论文或题解会容易很多Beats 的核心同样是“能整体处理就整体处理不能就递归靠势能分析保证复杂度”。另一个延伸点是“标记的语义设计”。曾经有段时间我写线段树总是下意识地认为标记必须“简单可合并”。但 UOJ170 告诉我标记本身也可以携带历史信息比如 hadd 只是一个普通的整数它描述的并非当前状态而是“从上次下传到现在的最值信息”。掌握了这种思路很多进阶数据结构的标记设计都变得有迹可循。比如可持久化线段树处理历史版本的 lazy也是类似的“额外记录一个过往峰值”的想法。如果你是在线上去 UOJ 交这道题建议先用小数据随机对拍把自己的代码和一份暴力线段树或者直接数组模拟对比。这类题的正确性关键是标记处理而不是线段树本身。对拍脚本生成 n 在 20 以内操作次数 2000 的随机数据几秒钟就能把你隐藏 bug 跑出来。我当时也是靠对拍才把 hadd 下传的 bug 揪出来的。7. 一个辅助理解的小例子为了把抽象的东西讲清楚我习惯用一个很小的例子跑一遍。设序列为 [5, 3]执行一次区间加 4再执行一次区间取模 5最后查询历史最大值。初始节点 root区间 [1,2] sum8mx5hmx5add0hadd0。区间加 4 sum16mx9hmx9add4hadd4。此时叶子上的真实值左叶子 9右叶子 7。因为 add 没下传它们本身的 mx 还是 5 和 3但父亲的 mx9 已经由 apply_add 算出来了。现在执行区间取模 5递归到 root root.mx9 5不能剪枝。先 pushdown 左儿子 apply_add(4, 4)mx 从 5 变 9hmx 从 5 变 max(5, 54)9sum9add4hadd4。 右儿子 apply_add(4, 4)mx 从 3 变 7hmx 从 3 变 max(3, 34)7sum7add4hadd4。 root.addroot.hadd0。 然后递归修改左儿子 [1,1]左儿子的 mx9 5进入叶子取模后左儿子 mx4sum4hmx 保持 max(9, 4)9。 右儿子同理mx 从 7 变 2hmx 保持 7。 递归返回 rootpull root.mx max(4, 2) 4 root.sum 6 root.hmx max(9, 7) 9最终历史最大值是9正确。注意左儿子的 hmx 是 9因为它曾经通过区间加达到 9取模后当前值降到 4但历史记录还保留 9。这就是历史最大值不回退的本质。如果你在这个过程里让 hmx 随取模变 4那答案就会错成 4 或 7这题就废了。这个例子跑完你基本能理解为什么需要 hadd。如果没有 haddpushdown 时只传 add4 给儿子儿子的 hmx 确实也能从 5 更新到 9因为 add4 时hv 恰好也是 4。但如果历史曾加过 100后来当前 add 变成 -50只传 add-50 就不可能让儿子的 hmx 更新到旧峰值必须把 hadd100 一起传下去。8. 这题的题解视角与最终体会我写 UOJ170 断断续续花了两天第一版代码 150 行第二版重构后压到 120 行核心问题不在行数而在状态设计。一旦想清了“当前最大值、历史最大值、当前加标记、历史最大加标记”这四个东西的关系整棵线段树就活了。它们两两配对mx 和 add 管现在hmx 和 hadd 管历史。每一次操作都要同时维护这两对关系缺一不可。从题目难度看UOJ170 不算最变态的那类题但它的考察点非常综合势能分析、标记合并、递归剪枝、类型选择几乎把一个进阶线段树该有的难点都覆盖了。如果你能把这道题从思路到代码完整吃透我建议你马上找几道 Segment Tree Beats 的题练手比如 SPOJ GSS 系列里的某些变种或者 Codeforces 上带区间取模和区间最值查询的题。你会发现自己对“信息聚合”的理解比之前深了不止一个层次。关于调试再分享一个亲测有效的小技巧调试这类线段树可以把查询和更新的 log 都打出来每执行完一个操作就打印整棵树的节点信息然后手动推演几组小数据对比。虽然麻烦但能很快暴露“标记忘下传”或“hadd 用了当前 add 而不是历史 add”这类问题。等对拍跑稳了再取消 log交上去基本就是一遍过。最后提醒一句UOJ 上的题评测机配置和时限都比较严格如果发现自己的写法在极限数据下跑到了 1.5 秒左右优先检查 pushdown 和递归是否有冗余调用把if (tr[p].add 0 tr[p].hadd 0) return;这种常数优化加好再考虑别的优化手段。线段树的常数优化往往比算法层面的改动更立竿见影。这题给我最大的收获不是会写某种线段树而是建立了一种“状态机思维”每个节点不只是存一个值而是一组在操作下同步演化的变量。当你把每个变量的更新规则都定义清楚代码自然就顺了。 线段树进阶：区间取模与历史最大值的标记设计与复杂度分析
1. 这题到底在考什么UOJ170 的题目认知UOJ170Picks loves segment tree VIII是 UOJ 上“线段树”系列里非常经典的一道题。如果你在 OJ 上刷到它第一眼看到的是一棵长度为 n 的序列、区间加、区间取模、区间求和、区间历史最大值这类操作可能以为只是普通线段树套个 lazy 就能过。实际做下去才会发现它最核心的难点根本不是“会不会写线段树”而是“怎么在同一棵线段树上同时维护取模、历史最大值和区间求和并且保证复杂度可控、标记之间不打架”。这个系列题目里VIII 的特别之处在于取模操作带来的非单调性变化会让普通的懒标记失效。你没法像区间加、区间赋值那样直接对线段树节点记录一个“待下传的修改”因为取模之后节点存的最大值、次大值、和、历史最大值都会发生不规则变化。很多第一次接触这道题的人包括我自己第一版代码都是拿“节点维护 max遇到区间取模就暴力递归到叶子”的方案去写结果要么 TLE要么在极端数据下复杂度退化到不可接受。完整题目约束是这样的维护一个长度为 n 的序列支持区间加、区间取模、区间求和、区间历史最大值就是每个位置从开始到现在出现过的最大值的总和或者区间最大值的历史峰值这里描述以题面为准UOJ170 的题面定义需要对照原题确认但大致方向是这几种操作的组合。n、操作次数在 1e5 级别值域可能在 1e9 左右。也就是说必须在 O((nq) log n) 或接近这个量级的复杂度内解决任何退化成 O(nq) 的暴力都不能接受。这篇文章我不会直接贴一份完整 AC 代码了事那没意义。我要拆的是思路链路为什么普通线段树处理不了取模操作到底破坏了什么历史最大值的维护为什么需要“标记减法”而不是简单的覆盖以及最终实现里值得注意的关键细节。适合的读者是有线段树基础、会 Pushdown、会懒标记但第一次遇到“多标记叠加 历史值”这类组合问题的选手。如果你能独立把这道题写对你对线段树的理解会上一个台阶后面再看什么 Segment Tree Beats、吉老师线段树都会轻松很多。2. 线段树处理这类题的基本盘2.1 为什么取模操作如此特殊常规线段树的区间修改可以被抽象成“节点的聚合信息经过某种统一函数变化”。区间加max 直接加 xsum 直接加 lenx非常好算。区间赋值max 变成 xsum 变成 lenx也好算。这些操作的共同点是节点内部所有元素满足某种一致性使得你只需要在节点层面记录一个修改标记不用下钻到叶子就能算出新的聚合值。取模彻底打破了这种一致性。假设节点维护的区间里最大值是 10次大值是 3区间和是 30。现在要对这个区间每个数取模 modmod 是 7。那么 10%733%73结果最大值变成了 3次大值还是 3区间和需要遍历所有叶子才能精确算出来。只靠 max 和次大值你根本不知道每个小于 mod 的数是否没变、哪些数变了多少。最关键的问题是取模操作让节点信息的“可预测性”崩塌。你无法用一个简单的标记把“区间里所有数对 x 取模”这件事记录下来等着查询时再算——因为作用于不同叶子上的效果不同取决于每个叶子的原始值。所以这类题的设计思路就是“部分递归 剪枝”。核心思想借鉴了 Segment Tree Beats 里“势能分析”的套路虽然取模对整段区间不可统一计算但如果我能判断这段区间“取模后不会发生变化”就可以直接跳过如果会发生变化就向下递归直到某个粒度上可以整体处理。什么时候区间取模可以整体跳过一个常见的充分条件是区间最大值小于模数。此时区间内所有元素都小于 mod对任何数取模都等于它本身操作无效。另一个稍微不常见但可用的条件是区间最大值和次大值的关系配合标记合并后或许能成段处理但在 UOJ170 里因为有区间加和历史最大值直接用 maxmod 作为剪枝条件是最稳妥的。2.2 历史最大值的维护为什么棘手普通线段树维护区间最大值只要每次更新后取个 max 就行。但“历史最大值”要求记录的是过去某个时刻的峰值。你可以理解成每个位置有一个“记录仪”每当当前位置的值发生变化记录仪就更新一次保存曾经到过的最大值。查询的时候问的是某段区间内这些记录仪的总和或最大值取决于题面具体定义。问题在于当你对一个区间加 x 时不仅当前值变了历史最大值也可能要变。当前值加上 x 后如果超过了历史峰值那么历史峰值更新为新值。这个“新值”可以用公式表达历史最大值 max(旧历史最大值, 旧当前最大值 x)。只要节点里同时维护当前最大值和历史最大值区间加这个操作是可以 O(1) 处理的。但一旦和取模混在一起事情就复杂了。取模会降低当前值但历史最大值不应该降低——历史记录是“曾经达到过”不会因为当前变小而回退。所以取模后节点的历史最大值可能保持不变也可能某个元素的历史最大值没有超过当前记录于是不更新。这里形成了双层状态当前值在变历史值在根据“是否超过峰值”决定更新。更麻烦的是懒标记的叠加。2.3 懒标记的加法问题假设父节点有一个区间加标记 add下传到子节点时子节点也积累了自己的 add。这是线段树的基本操作。但历史最大值的懒标记不能只是“accumulate add”因为历史最大值记录的是“曾经达到过”所以你需要另一个标记专门表示“从上次 pushdown 到现在子节点曾经接收到过的最大加值”。这个标记通常叫 mx_add 或 his_add。父节点向子节点下传时不能只把当前 add 累加到子节点还要把父节点的 mx_add历史最大加值与子节点当前的 mx_add 比较更新子节点的 mx_add。然后子节点的历史最大值要用“当前值 父节点历史最大加值”来更新。听起来还行因为区间加是线性的。可一旦区间取模进入add 标记和取模的顺序关系就变得极其微妙取模和加法的先后顺序不同结果是不同的。你无法用一个 add 标记概括“先加再取模”或“先取模再加”的操作序列。这就是 UOJ170 真正的考验不是线段树模板而是标记体系设计。3. 线段树节点状态与标记体系设计3.1 节点需要维护哪些字段在动手写代码前先把节点要维护的信息一条条列清楚。我 C 的 struct 通常长这样struct Node { long long sum; long long mx; // 当前区间最大值 long long hmx; // 历史区间最大值 long long add; // 当前加标记 long long hadd; // 历史最大加标记 };这里 sum 是区间和mx 是当前最大值hmx 是历史最大值。add 表示“子节点还没接收的加法量”hadd 表示“最近一次 pushdown 之后add 曾经达到过的最大值”。这两个加标记是配套的缺一个历史最大值就没法维护。有的写法还会额外加一个 set 标记或者 second_mx用来处理区间赋值或者取模加速。但在取模场景下靠 mx 剪枝已经能保证复杂度不是非要 second_mx 不可。引入 second_mx 会增加 pushdown 复杂度若处理不好反而容易出 bug。UOJ170 的题解里有基于 Segment Tree Beats 的第二种做法就是维护“最大值、次大值、最大值个数”以期在取模时批量更新但那种做法对标记下传要求更高初学不建议。3.2 区间加操作的信息更新对节点 p 执行一次“区间加 x”更新公式是node[p].hmx max(node[p].hmx, node[p].mx x); node[p].mx x; node[p].sum x * len(p); node[p].hadd max(node[p].hadd, node[p].add x); node[p].add x;前两行好理解先看看加上 x 后能不能刷新历史最大然后更新当前最大值。第三行朴素更新和。关键在第四行为什么 hadd 也要更新因为 add 这个标记本身累加了操作而 hadd 记录的是 add 曾经到达过的最大值。为什么要记录曾经的最大值因为这决定了下传时子节点的历史最大能推到多少。如果父节点曾经加过 100后来某个操作又减回去了这里虽然题目是区间加加的可以是负数当前 add 也许只有 0但历史上加过 100 这件事必须原封不动传给子节点否则子节点的历史最大值就漏了一段过去。3.3 区间取模操作的信息更新取模把加法标记体系彻底打乱了。一个常见的错误处理方式是“取模后直接把 add 清零”。表面看节点所有数都取模了之前累积的加法量已经没有意义清零似乎合理。但问题在于取模前子节点可能还没收到过父节点的 add而取模这个操作本身又不能简单地下传为“子节点共享的一个标记”。如果你在父节点清了 add那子节点就永远失去了这段加法信息历史最大值必然算错。所以取模操作必须递归处理。到了某个节点 p操作是“区间内所有数对 mod 取模”先看剪枝条件如果 node[p].mx mod直接返回因为所有数取模都不变。否则如果 p 是叶子直接更新叶子的值sum mx hmx (原值 % mod)这里有个细节——历史最大值 hmx 要不要跟着变成原值 % mod注意hmx 记录的是历史最大它不受当前取模影响。比如某个位置历史最大是 100当前值是 5现在对 5 取模还是 5历史最大依然是 100。除非题目定义“历史最大值”是“当前值变化后的最大值减去什么别的偏移”UOJ170 具体定义需要对照题面确认但标准历史最大值含义是不回退的否则 hmx 不需要因为取模而下降。而 mx 是当前最大值必须更新为取模后的新值。取模后新 mx 可能比旧 mx 小很多这时用旧 hmx 去和它比对保持 hmx max(旧 hmx, 新 mx) 即可。如果这个节点不是叶子但满足 mx mod直接返回否则继续向下递归左右儿子然后再 pull 更新当前节点。这个递归过程会一路下钻到所有“最大值大于等于 mod”的叶子或可处理子区间。3.4 pushdown 的正确顺序一旦一个节点既有 add 标记又有待下传的子节点数据pushdown 的调用顺序就是生死攸关的。我的 pushdown 逻辑是void pushdown(int p, int l, int r) { if (node[p].add 0 node[p].hadd 0) return; int mid (l r) 1; apply_add(left_child, node[p].add, node[p].hadd, mid - l 1); apply_add(right_child, node[p].add, node[p].hadd, r - mid); node[p].add node[p].hadd 0; }apply_add 函数就是 3.2 里的那四行更新但要把 x 换成传入的 add把 hadd_add 换成传入的 hadd。注意下传时要分别传“当前加法量”和“历史最大加法量”并用它们去更新子节点的当前最大值、历史最大值、当前加标记、历史最大加标记。顺序上先更新 hmx 和 hadd再更新 mx 和 add。这只是公式书写顺序实际效果是同时发生的。问题来了在区间取模的递归过程中如果走到一个节点需要先递归修改子树那在递归之前必须先 pushdown把父节点积压的 add 传给儿子否则儿子的 mx 是“旧值”取模判断可能出错。这个 pushdown 是必须写在取模递归函数里的不是在外部提前统一 pushdown。同理区间加和区间查询也必须先 pushdown。4. 完整实现链路从暴力思维到可AC代码4.1 线段树基础框架这里直接给出一份可参考的核心实现我用的是数组存树方便调试也方便阅读。注意这只是核心代码完整 AC 需要自己套上输入输出、建树等模板。const int MAXN 100005; struct Node { long long sum, mx, hmx; long long add, hadd; } tr[MAXN 2]; void apply_add(int p, int len, long long v, long long hv) { tr[p].hmx max(tr[p].hmx, tr[p].mx hv); tr[p].mx v; tr[p].sum v * len; tr[p].hadd max(tr[p].hadd, tr[p].add hv); tr[p].add v; } void pushdown(int p, int l, int r) { if (tr[p].add 0 tr[p].hadd 0) return; int mid (l r) 1; apply_add(p 1, mid - l 1, tr[p].add, tr[p].hadd); apply_add(p 1 | 1, r - mid, tr[p].add, tr[p].hadd); tr[p].add tr[p].hadd 0; } void pull(int p) { tr[p].sum tr[p 1].sum tr[p 1 | 1].sum; tr[p].mx max(tr[p 1].mx, tr[p 1 | 1].mx); tr[p].hmx max(tr[p 1].hmx, tr[p 1 | 1].hmx); }apply_add 里的 hv 是“历史最大加值”不是当前加值。当父节点下传时hv 用父节点的 haddv 用父节点的 add。这保证了子节点知道“过去最大被加了多少”从而能刷新子节点的 hmx。4.2 区间取模的递归实现void modify_mod(int p, int l, int r, int ql, int qr, long long mod) { if (qr l || r ql) return; if (ql l r qr tr[p].mx mod) return; if (l r) { long long val tr[p].mx; // 叶子当前值 // 这里要注意sum 和 mx 是同一个数取模后直接更新。 // hmx 保留历史最大值如果取模后的值能超过 hmx再更新。 tr[p].mx val % mod; tr[p].sum tr[p].mx; tr[p].hmx max(tr[p].hmx, tr[p].mx); // 取模是否要更新 add/hadd不需要因为叶子没有下传子节点的问题。 // 但叶子可能保留着未清零的 add 标记在实际调用前必须已经 pushdown 过 // 即所有 add 都应用于当前真实值了所以这里可以直接用 tr[p].mx。 return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) modify_mod(p 1, l, mid, ql, qr, mod); if (qr mid) modify_mod(p 1 | 1, mid 1, r, ql, qr, mod); pull(p); }这里有个容易忽略的点叶子节点也可能带着 add 标记。所以在进入叶子之前pushdown 必须已经把这个节点所有祖先的标记一路传下来。我的写法里递归进入儿子前都会 pushdown 当前节点所以到达叶子时叶子上的 add 已经清零或已经应用到真实值中。但还有一种情况如果在叶子节点上直接执行区间加而叶子节点本身的 add 不为 0因为有些维护方式不 pushdown 到叶子那就要先应用 add 再取模。稳妥起见在 modify_mod 里遇到非叶子节点时先 pushdown叶子节点就假设 add 已经全部应用。如果是为了绝对安全你也可以在叶子分支里写成tr[p].mx (tr[p].mx tr[p].add) % mod; tr[p].add 0;但要小心tr[p].add 可能是之前累积的、未被应用到 mx 上的标记。一旦 add 先应用再取模hadd 的历史是否受影响叶子没有孩子hadd 理论上就不用关心了可以清空。不过这个分支在实际中不会触发因为我所有更新路径都会在递归深处提前 pushdown。4.3 区间加和查询的实现区间加就是标准写法但要记得同时更新 hadd。区间查询如果只查 sum只 pull sum 就行如果查历史最大值的区间和或最大值需要 pushdown 保证儿子拿到历史标记。void modify_add(int p, int l, int r, int ql, int qr, long long v) { if (ql l r qr) { apply_add(p, r - l 1, v, v); return; } pushdown(p, l, r); int mid (l r) 1; if (ql mid) modify_add(p 1, l, mid, ql, qr, v); if (qr mid) modify_add(p 1 | 1, mid 1, r, ql, qr, v); pull(p); }注意 apply_add 里 hv 传的是 v因为对于一次性区间加操作它既是当前加值也是历史最大加值。这和 pushdown 时传 tr[p].add 和 tr[p].hadd 不同pushdown 的 hv 是父节点曾经达到的最大加值而 v 是父节点当前剩余加值。看到这里可能有人问为什么 pushdown 时 hv 传 hadd 就能覆盖子节点的历史想象父节点曾经 add 到 10然后减到 -5当前 add 是 -5。子节点接到下传时得到 v-5 和 hv10。子节点 hmx 用 mx 10 去更新这等于把父节点历史上“加得最多的那一刻”也考虑进去了。如果只传 -5子节点历史最大值会漏掉加 10 那段时间。这是整个标记设计最精妙也最容易错的地方。4.4 复杂度为什么是对的很多人看到区间取模一路递归到叶子觉得最坏复杂度会爆炸。但取模有一个重要性质如果 x mod m 发生了变化那么新值一定小于等于 x/2。因为当 x m 时x mod m m x/2最后一个不等号成立需要 m x/2如果 m x/2则 x mod m x - m x/2仍然成立。这意味着每个位置的有效取模次数是 O(log value) 级别的。每次区间取模递归到叶子至少让某些位置的值减半所以总递归次数约为 O((nq) log max_value)。再加上线段树的 log n 结构整体复杂度可以认为是 O((nq) log n log value) 量级在 1e5 数据上足够通过。这也是这类题“看似暴力递归实则势能分析保证复杂度”的典型套路。真正容易 TLE 的写法是不加 mx mod 剪枝直接全叶子递归那样复杂度就是 O(nq)谁写谁挂。5. 实现中遇到的坑与排查思路5.1 历史最大标记在取模后要不要修改这个坑我在初版代码里踩得很实。最开始我实现叶子取模时直接写了tr[p].hmx tr[p].mx % mod也就是让历史最大值随着当前值取模了。样例过了因为样例里的历史最大值一直处在递增状态取模后正好没触发回退。但数据一大就 WA最后查出来是历史最高纪录被取模“抹掉”了完全违背了历史最大值的定义。经验是历史最大值只在“当前值超过旧纪录”时更新其他任何时候都不应该被直接拉低。取模是一个拉低当前值的操作所以 hmx 在这个操作中最多是不变不会变小。如果你在代码里看到 hmx 由于取模而变小几乎可以断定逻辑错了。5.2 pushdown 时 hadd 的初始值另一种常见 bug 是 hadd 初始值设成了负无穷或 0。想想看如果 add 标记允许出现负数那么 hadd 记录的是 add 曾经到达过的最大值。当初始时 add0hadd 也应该是 0因为“当前没有加过任何数历史上的最大加值至少是 0”。但如果某个节点一开始就收到一个负数加操作比如 v -3那么 add 变成 -3hadd 应该变成 max(0, -3) 0也就是历史最大加值是 0表示没有加过正数。这合理吗假设某个位置初始值是 10执行区间加 -3当前值变成 7历史最大值保持 10因为 10 已经是历史峰值。子节点下传时如果 hadd 传 0子节点的 hmx 用 mx 0 去更新不会把 10 丢失因为 10 已经在子节点的 hmx 里了。所以 hadd 初始为 0 是对的因为“没有加法操作”也是一个合法状态历史最大加值最小就是 0。但这里有个隐藏前提如果所有数都是负数初始值也是负数那么历史最大加值可能是正数吗仔细想历史最大值记录的是位置上的值不是加法的总和。一个位置初始是 -100之后加了 -5当前值 -105历史最大值仍是 -100。如果用 mx hadd 去更新 hmxhadd 是 0得到 max(-100, -105) -100正确。所以即使数值全程为负hadd 0 依然能正确恢复历史峰值因为初始值已经在 hmx 里。结论hadd 初始化为 0 即可不需要负无穷。5.3 取模递归深处重复 pushdown 导致标记错误递归实现里我通常在进入左右儿子前调用 pushdown但有的写法是在函数开头无条件 pushdown。这两者的差别很大如果是区间查询你 pushdown 后儿子拿到标记是对的。但如果是区间取模递归到某个区间完全覆盖、且 mx mod 时你提前 pushdown 就等于把父节点标记白白下发增加不必要的时间开销而且还要在返回后重新 pull。虽然不一定错但常数会变大本身就有 TLE 风险。更严重的写法是在取模分支中先判断 ql l r qr mx mod 就 return但这个 return 之前没有 pushdown。看起来没错因为剪枝的前提是当前节点的 mx 已经包含了所有 add 标记。节点在 pull 之后mx 是儿子 mx 的最大值而这个 mx 已经包含了儿子上的 add。所以当前节点的 mx 是正确的直接用即可。但如果当前节点本身还挂着一个 add 没下传mx 也已经被这个 add 更新过了因为 apply_add 更新节点时会同步更新 mx。所以剪枝条件不依赖 pushdown没问题。真正需要 pushdown 的场景是你必须修改儿子的具体值且儿子的状态可能和父节点标记冲突。例如取模递归到儿子前父节点还有 add 没传儿子记录的 add 是旧状态这时候你直接递归会导致儿子取模时用错误的基础值。我的建议是在每个递归函数的开头如果没有提前返回就只对非叶节点调用一次 pushdown。类似这样if (ql l r qr tr[p].mx mod) return; pushdown(p, l, r);这样能保证所有需要修改的路径上标记都是干净的。5.4 查询历史最大值时忘记 pushdown区间求和普遍不会忘记 pushdown因为不 pushdown 也能得到“带标记的 sum”而标记本身已经更新了 sum所以查询结果看起来是对的。但历史最大值的查询就不同了如果你只把某个节点的 hmx 返回而没有下放父节点的 hadd那么这个 hmx 可能漏掉“父节点历史上曾加过的最大值”。因为父节点的 hadd 会刷新子节点的 hmx只有在下传时才发生。查询路径上必须把一路上的标记全部 pushdown 下去才能保证子节点 hmx 是最新的。这个坑非常隐蔽单点查询历史最大值时你会习惯性地从根节点走到叶子走到哪 pushdown 到哪但如果查询区间正好覆盖某个节点你可能直接返回 tr[p].hmx忘了它的祖先还有 hadd 没传。正确写法是查询函数在进入子区间前必须 pushdown即使完全覆盖只要父节点存在未下传标记也需要先下传再返回或者返回时手动用祖先 hadd 更新答案但那样很绕不如直接下传。5.5 long long 是底线序列元素在 1e9 级别但区间加和操作会累计历史最大值也只在 1e9 到 2e9 徘徊。但区间和呢n1e5值1e9区间和的最大值能到 1e14不用 long long 必炸。这个问题在写第一版时我就吃过亏int 存 sum结果一组大数据直接 out。除了 summx 和 hmx 也要 long long因为经过多次加法累加后单点值也有可能超过 int 范围。所有标记 add 和 hadd 同样 long long。5.6 取模的边界细节取模操作中的模数可能比所有数都大这样每个节点都满足 mx mod所有调用都是 O(1) 剪枝非常舒服。但模数也可能等于 1此时任何整数取模后都是 0。如果一开始 mx 是 5mod 是 1mx mod递归到叶子叶子值变 0。后续再取模mx 是 0小于 mod直接返回。所以不会被卡到 O(nq)。还有一种边界是取模超大但当 mod 大于 mx 时剪枝所以没问题。唯一的风险是模数为 0这在题目里应该不会出现如果出现了取模本身无意义要在输入时过滤掉否则除以 0 直接 RE。5.7 快速排查清单我把调试过程中用的检查点整理成一张表写题时照着过一遍能省很多时间检查点正确做法典型错误hadd 初始化初始为 0设为负无穷区间加更新hmx max(hmx, mx v)mx vhadd 同步更新只更新 mx 和 sum忘掉 hmx/haddpushdown 下传同时传 add 和 hadd只传 add历史最大值漏更新取模剪枝条件节点 mx mod 直接返回不加剪枝暴力递归叶子取模hmx 保持历史mx/sum 用取模后值hmx 随取模变小查询历史路径上先 pushdown直接返回节点 hmxsum 类型long longint 溢出6. 进一步思考从 UOJ170 到 Segment Tree Beats写这道题的过程中你会逐渐意识到一个更高级的线段树形态不只是维护区间最值和历史最值而是维护“最大值、次大值、最大值个数”然后通过三类标记实现更快的区间修改。这类线段树被通称为 Segment Tree Beats是吉如一老师提出的。UOJ170 其实并不是最经典的 Beats 题因为它的取模剪枝靠的是“值减半”的自然势能而不是严格的最大值次大值势能。但如果你理解了拿 mx 做剪枝的思路再去看 Beats 的论文或题解会容易很多Beats 的核心同样是“能整体处理就整体处理不能就递归靠势能分析保证复杂度”。另一个延伸点是“标记的语义设计”。曾经有段时间我写线段树总是下意识地认为标记必须“简单可合并”。但 UOJ170 告诉我标记本身也可以携带历史信息比如 hadd 只是一个普通的整数它描述的并非当前状态而是“从上次下传到现在的最值信息”。掌握了这种思路很多进阶数据结构的标记设计都变得有迹可循。比如可持久化线段树处理历史版本的 lazy也是类似的“额外记录一个过往峰值”的想法。如果你是在线上去 UOJ 交这道题建议先用小数据随机对拍把自己的代码和一份暴力线段树或者直接数组模拟对比。这类题的正确性关键是标记处理而不是线段树本身。对拍脚本生成 n 在 20 以内操作次数 2000 的随机数据几秒钟就能把你隐藏 bug 跑出来。我当时也是靠对拍才把 hadd 下传的 bug 揪出来的。7. 一个辅助理解的小例子为了把抽象的东西讲清楚我习惯用一个很小的例子跑一遍。设序列为 [5, 3]执行一次区间加 4再执行一次区间取模 5最后查询历史最大值。初始节点 root区间 [1,2] sum8mx5hmx5add0hadd0。区间加 4 sum16mx9hmx9add4hadd4。此时叶子上的真实值左叶子 9右叶子 7。因为 add 没下传它们本身的 mx 还是 5 和 3但父亲的 mx9 已经由 apply_add 算出来了。现在执行区间取模 5递归到 root root.mx9 5不能剪枝。先 pushdown 左儿子 apply_add(4, 4)mx 从 5 变 9hmx 从 5 变 max(5, 54)9sum9add4hadd4。 右儿子 apply_add(4, 4)mx 从 3 变 7hmx 从 3 变 max(3, 34)7sum7add4hadd4。 root.addroot.hadd0。 然后递归修改左儿子 [1,1]左儿子的 mx9 5进入叶子取模后左儿子 mx4sum4hmx 保持 max(9, 4)9。 右儿子同理mx 从 7 变 2hmx 保持 7。 递归返回 rootpull root.mx max(4, 2) 4 root.sum 6 root.hmx max(9, 7) 9最终历史最大值是9正确。注意左儿子的 hmx 是 9因为它曾经通过区间加达到 9取模后当前值降到 4但历史记录还保留 9。这就是历史最大值不回退的本质。如果你在这个过程里让 hmx 随取模变 4那答案就会错成 4 或 7这题就废了。这个例子跑完你基本能理解为什么需要 hadd。如果没有 haddpushdown 时只传 add4 给儿子儿子的 hmx 确实也能从 5 更新到 9因为 add4 时hv 恰好也是 4。但如果历史曾加过 100后来当前 add 变成 -50只传 add-50 就不可能让儿子的 hmx 更新到旧峰值必须把 hadd100 一起传下去。8. 这题的题解视角与最终体会我写 UOJ170 断断续续花了两天第一版代码 150 行第二版重构后压到 120 行核心问题不在行数而在状态设计。一旦想清了“当前最大值、历史最大值、当前加标记、历史最大加标记”这四个东西的关系整棵线段树就活了。它们两两配对mx 和 add 管现在hmx 和 hadd 管历史。每一次操作都要同时维护这两对关系缺一不可。从题目难度看UOJ170 不算最变态的那类题但它的考察点非常综合势能分析、标记合并、递归剪枝、类型选择几乎把一个进阶线段树该有的难点都覆盖了。如果你能把这道题从思路到代码完整吃透我建议你马上找几道 Segment Tree Beats 的题练手比如 SPOJ GSS 系列里的某些变种或者 Codeforces 上带区间取模和区间最值查询的题。你会发现自己对“信息聚合”的理解比之前深了不止一个层次。关于调试再分享一个亲测有效的小技巧调试这类线段树可以把查询和更新的 log 都打出来每执行完一个操作就打印整棵树的节点信息然后手动推演几组小数据对比。虽然麻烦但能很快暴露“标记忘下传”或“hadd 用了当前 add 而不是历史 add”这类问题。等对拍跑稳了再取消 log交上去基本就是一遍过。最后提醒一句UOJ 上的题评测机配置和时限都比较严格如果发现自己的写法在极限数据下跑到了 1.5 秒左右优先检查 pushdown 和递归是否有冗余调用把if (tr[p].add 0 tr[p].hadd 0) return;这种常数优化加好再考虑别的优化手段。线段树的常数优化往往比算法层面的改动更立竿见影。这题给我最大的收获不是会写某种线段树而是建立了一种“状态机思维”每个节点不只是存一个值而是一组在操作下同步演化的变量。当你把每个变量的更新规则都定义清楚代码自然就顺了。