# 格兰之森 题解 ## 解法与取舍 **出题人解法：每条重链独立分块。** 逐链分块作为标程。全局分块少建一些小块和容器，测量中的峰值内存较低；但短链修改可能重建同一块内其他链的节点。在参考环境的 1.0 秒时限下，随附的全局分块程序在平衡树用例上超时。它作为时间与空间取舍的方案介绍，不能直接用于通过完整数据。 **程序与署名：** [std.cpp](std.cpp) 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的全局分块见 [alternative.cpp](alternative.cpp) 和[时间与空间取舍方案题解](solution-alternative.zh.md)。 ## 把树路径拆成区间 对每个连通块任选根，计算父亲、深度、子树大小和最大子树对应的重儿子。让每条重链上的节点在一个线性数组中连续排列。 任意简单路径可拆成 $O(\log(n+1))$ 段重链区间。每次从链头较深的端点向上处理，直到两个端点在同一条链。处理的是点权，因此最后一段包含两个端点，也包含最近公共祖先，且各段互不重叠。 参考程序先显式遍历森林，再逆序计算子树大小；重链编号也使用循环，避免长链递归。 ## 每个块维护什么 对每条长度为 $L$ 的重链，单独取块长 $B=\lceil\sqrt L\rceil$ ，块不跨链。每块保存原顺序值、排序值及其前缀和，还保存两种互斥状态： - 有赋值标记：本块所有当前值均为标记值；排序数组暂时不用。 - 无赋值标记：当前值等于原顺序值加上统一的加法标记。 整块赋值会设置赋值标记并把加法标记清零。整块加法若遇赋值标记，就增加赋值标记；否则增加加法标记。局部修改前先把当前真实值写回整个块，清除标记，然后修改所需位置并重新排序、计算前缀和。这样赋值会覆盖此前加法，后来的加法仍正确作用于已赋值的块。 ## 门槛查询 对赋值块，直接判断其唯一当前值是否达到门槛，乘以本次覆盖的元素数。 对没有赋值标记的完整块，设加法标记为 $a$ ，门槛为 $d$ .在排序值中二分第一个不小于 $d-a$ 的位置。它之后的元素数就是计数；这些原值的后缀和加上“计数乘 $a$”就是当前权值和。 不完整块直接逐个检查真实值。权值为负时仍按同一个比较处理；达到门槛的数值和可以为负，不能截断到零。 ## 正确性与复杂度 块的不变量保证每种标记状态都精确表示当前权值。全块或局部修改保持该不变量；二分只把门槛减去统一加法，没有改变选中集合。将互不重叠的重链区间答案相加，恰好得到整条路径的答案。 若一条路径经过 $h$ 条重链，第 $j$ 条链长为 $L_j$ 、块长为 $B_j=\lceil\sqrt{L_j}\rceil$ ，四类操作均可用以下保守上界覆盖： $$O\!\left(\sum_{j=1}^{h}\left(\frac{L_j}{B_j}+B_j\right)\log(B_j+1)\right)$$ 其中 $h=O(\log(n+1))$ ，且这些链互不相交，故 $\sum_j L_j\le n$ .由柯西不等式，还可将其界为 $O(\sqrt{n\log(n+1)}\log(n+1))$ .初始化为 $O(n\log(n+1))$ 的上界，空间为 $O(n)$ ；全部 $q$ 次操作的时间再加上对应单次上界之和。 任意当前点权的绝对值不超过 $10000(q+1)$ ，路径和的绝对值不超过 $10000n(q+1)$ .点权、标记和前缀和均使用 64 位整数。 ## 理论复杂度与实际耗时 本题提供了一个能拉开差距的对照：同一份五十万节点平衡树用例上，逐链分块约为 0.230 秒，全局分块约为 1.973 秒。不同于只在浅深度范围内多做几轮整数查询，本题的额外开销会反复重建整段数组。 该生成用例的树高为 18 条边，任意重链至多含 19 个点。逐链分块方案的链内块长至多为 $\lceil\sqrt{19}\rceil=5$ ；全局版仍取 $\lfloor\sqrt{500000}\rfloor=707$ .跨越多条短链的路径修改，在每段边界只改几个位置，也可能要求全局版把包含其他链的整个块还原、排序并重算前缀和。赋值、加法的标记仅能省掉完全覆盖块的这部分工作。 因此，本例有明确的数据形状让额外工作反复发生，时间差也已在同输入上测得。全局版建立的块与容器更少，仍有峰值内存较低的好处；但这不足以保证它能满足当前 1.0 秒时限。这个对照说明应查看具体输入触发了哪些操作，不能从前三题的结果推断“多一个对数通常无关紧要”。块长差别可由实现和生成器核实；没有单独测量各阶段耗时，不把全部时间差归给排序一项。 ## 验证与性能 各方案的五次重复计时与峰值内存记录见[评测环境与性能](../../../docs/评测环境与性能.md)。