# 格兰之森 题解

> 时间与空间取舍方案：全局分块。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。

解法贡献：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\!\left(\left(\frac nB+B\log(n+1)\right)\log(B+1)\right)$$

初始化耗时 $O(n\log(B+1))$ ，总时间为初始化加上 $q$ 倍上述上界，空间为 $O(n)$ .这份实现不是每次操作都只需对数时间的数据结构；平衡树上跨越多条重链的用例需要单独测量。

任意当前点权的绝对值不超过 $10000(q+1)$ ，路径和的绝对值不超过 $10000n(q+1)$ .点权、标记和前缀和均使用 64 位整数。

## 验证

独立检查使用普通路径搜索和逐点修改。覆盖多连通块、孤立点、负数、门槛相等、全块赋值后加法及跨块局部修改。最大规模包含链、星形、平衡树和随机树。

性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。

## 理论复杂度与实际耗时

五十万节点平衡树的每条重链至多含 19 个点，逐链块长至多为五，全局块长却为 707。短链上的局部修改因而可能多次重建很大的全局块，解释了测量中约 0.230 秒与 1.973 秒的同输入差距；本方案块对象较少、内存较低的优势仍保留。

完整的参数分析、操作统计和实测对照见[主方案题解](solution.zh.md#理论复杂度与实际耗时)。