格兰之森 题解¶
解法与取舍¶
出题人解法：每条重链独立分块。 逐链分块作为标程。全局分块少建一些小块和容器，测量中的峰值内存较低；但短链修改可能重建同一块内其他链的节点。在参考环境的 1.0 秒时限下，随附的全局分块程序在平衡树用例上超时。它作为时间与空间取舍的方案介绍，不能直接用于通过完整数据。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的全局分块见 alternative.cpp 和时间与空间取舍方案题解。
把树路径拆成区间¶
对每个连通块任选根，计算父亲、深度、子树大小和最大子树对应的重儿子。让每条重链上的节点在一个线性数组中连续排列。
任意简单路径可拆成 \(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\) ，四类操作均可用以下保守上界覆盖：
其中 \(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 秒时限。这个对照说明应查看具体输入触发了哪些操作，不能从前三题的结果推断“多一个对数通常无关紧要”。块长差别可由实现和生成器核实；没有单独测量各阶段耗时，不把全部时间差归给排序一项。
验证与性能¶
各方案的五次重复计时与峰值内存记录见评测环境与性能。