格兰之森 题解¶
时间与空间取舍方案：全局分块。Codex（GPT-6）采用的解法，程序见 alternative.cpp；与出题人解法的比较见主题解。
解法贡献：Codex（GPT-6）沿用重链剖分与排序分块的思路，重新实现显式森林遍历、全局分块和独立的赋值／加法标记，并补充两者组合的证明与复杂度。重链剖分和分块均为已有方法。
把树路径拆成区间¶
对每个连通块任选根，计算父亲、深度、子树大小和最大子树对应的重儿子。让每条重链上的节点在一个线性数组中连续排列。
任意简单路径可拆成 \(O(\log(n+1))\) 段重链区间。每次从链头较深的端点向上处理，直到两个端点在同一条链。处理的是点权，因此最后一段包含两个端点，也包含最近公共祖先，且各段互不重叠。
参考程序先显式遍历森林，再逆序计算子树大小；重链编号也使用循环，避免长链递归。
每个块维护什么¶
设块长为 \(B=\max(1,\lfloor\sqrt n\rfloor)\) .对线性数组按固定长度分块，每块保存原顺序值、排序值及其前缀和，还保存两种互斥状态：
- 有赋值标记：本块所有当前值均为标记值；排序数组暂时不用。
- 无赋值标记：当前值等于原顺序值加上统一的加法标记。
整块赋值会设置赋值标记并把加法标记清零。整块加法若遇赋值标记，就增加赋值标记；否则增加加法标记。局部修改前先把当前真实值写回整个块，清除标记，然后修改所需位置并重新排序、计算前缀和。这样赋值会覆盖此前加法，后来的加法仍正确作用于已赋值的块。
门槛查询¶
对赋值块，直接判断其唯一当前值是否达到门槛，乘以本次覆盖的元素数。
对没有赋值标记的完整块，设加法标记为 \(a\) ，门槛为 \(d\) .在排序值中二分第一个不小于 \(d-a\) 的位置。它之后的元素数就是计数；这些原值的后缀和加上“计数乘 \(a\)”就是当前权值和。
不完整块直接逐个检查真实值。权值为负时仍按同一个比较处理；达到门槛的数值和可以为负，不能截断到零。
正确性与复杂度¶
块的不变量保证每种标记状态都精确表示当前权值。全块或局部修改保持该不变量；二分只把门槛减去统一加法，没有改变选中集合。将互不重叠的重链区间答案相加，恰好得到整条路径的答案。
一条路径总共包含至多 \(n/B\) 个完整块，以及 \(O(\log(n+1))\) 个区间两端的碎块。完整块查询耗时 \(O(\log(B+1))\) ，局部修改重建一个块耗时 \(O(B\log(B+1))\) .因此一个同时涵盖四种操作的上界是
初始化耗时 \(O(n\log(B+1))\) ，总时间为初始化加上 \(q\) 倍上述上界，空间为 \(O(n)\) .这份实现不是每次操作都只需对数时间的数据结构；平衡树上跨越多条重链的用例需要单独测量。
任意当前点权的绝对值不超过 \(10000(q+1)\) ，路径和的绝对值不超过 \(10000n(q+1)\) .点权、标记和前缀和均使用 64 位整数。
验证¶
独立检查使用普通路径搜索和逐点修改。覆盖多连通块、孤立点、负数、门槛相等、全块赋值后加法及跨块局部修改。最大规模包含链、星形、平衡树和随机树。
性能测量见评测环境与性能。
理论复杂度与实际耗时¶
五十万节点平衡树的每条重链至多含 19 个点，逐链块长至多为五，全局块长却为 707。短链上的局部修改因而可能多次重建很大的全局块，解释了测量中约 0.230 秒与 1.973 秒的同输入差距；本方案块对象较少、内存较低的优势仍保留。
完整的参数分析、操作统计和实测对照见主方案题解。