题目解法：F. Farmer John's Favorite Function

一、核心数学观察

1.1 开方取整的等价性

由于我们只关心 $\lfloor f(n) \rfloor$，可以证明每一步都取整不影响最终结果的整数部分：

$$f(1) = \lfloor \sqrt{a_1} \rfloor$$ $$f(i) = \lfloor \sqrt{f(i-1) + a_i} \rfloor \quad (i > 1) $$

这样我们完全在整数域上操作，避免了浮点数精度问题。

1.2 前面元素的影响极其有限

关键结论：当 $n \ge 6$ 时，改变 $a_1$ 最多只会让 $\lfloor f(n) \rfloor$ 变化 $1$。

更一般地，对于任意连续的一段区间，前一个区间的结果只会让当前区间的结果要么不变，要么恰好增加 $1$。这个性质是解题的基础。

---

二、分块策略

2.1 块大小的选择

将数组分成大小为 $B = 6$ 的块。如果 $n$ 不是 $6$ 的倍数，在数组前面补 $0$ 使其成为 $6$ 的倍数。

选择 $B = 6$ 的原因：经过 $6$ 步递推后，前面值的影响被压缩到最多 $1$，这使得每个块的行为可以简化为两种可能。

2.2 块内信息提取

对于每个块 $[l, r]$，我们计算两个关键值：

$v$：假设 $f(l-1) = 0$ 时，计算得到的 $f(r)$ 的值

$$v = f(r) \text{ 当 } f(l-1) = 0$$

$c$：最小的非负整数，使得当 $f(l-1) = c$ 时，$f(r) = v + 1$

$c$ 可以通过从块内从右往左逆向计算得到：

• 设目标值为 $v+1$
• 逆向递推公式：进入第 $i$ 步前的值 $= (\text{离开第 } i \text{ 步后的值})^2 - a_i$
• 最终得到的值即为阈值 $c$

含义：

• 如果 $f(l-1) < c$，则 $f(r) = v$
• 如果 $f(l-1) \ge c$，则 $f(r) = v + 1$

如果逆向计算过程中值超过 $2 \times 10^9$，说明无论前面多大都无法让结果达到 $v+1$，此时 $c$ 视为无穷大。

---

三、块的合并规则

每个块用二元组 $(v, c)$ 表示。合并两个相邻块 $(v_1, c_1)$ 和 $(v_2, c_2)$ 时，结果 $(v, c)$ 分三种情况：

情况1：$v_1 < c_2 - 1$

• 左块输出最大为 $v_1 + 1$，仍然小于 $c_2$
• 右块输出始终为 $v_2$
• 合并后 $v = v_2$，$c = \infty$（无法触发 $v_2 + 1$）

情况2：$v_1 \ge c_2$

• 左块输出最小为 $v_1$，已经 $\ge c_2$
• 右块输出始终为 $v_2 + 1$
• 合并后 $v = v_2 + 1$，$c = \infty$

情况3：$v_1 = c_2 - 1$

• 左块输出为 $v_1$ 或 $v_1 + 1 = c_2$
• 当左块输出 $= v_1$（即输入 $y < c_1$）时，右块输出 $v_2$
• 当左块输出 $= c_2$（即输入 $y \ge c_1$）时，右块输出 $v_2 + 1$
• 合并后 $v = v_2$，$c = c_1$

---

四、数据结构维护

4.1 线段树维护块序列

将每个块视为线段树的一个叶子节点，存储其 $(v, c)$ 信息。内部节点存储左右子节点合并后的信息。

• 单点更新：修改数组元素后，重新计算所在块的 $(v, c)$，更新叶子节点并向上合并，复杂度 $O(\log n)$
• 整体查询：查询根节点，得到整个数组的 $(v, c)$，由于初始 $f(0) = 0$ 且通常 $0 < c$，答案即为 $v$

4.2 复杂度分析

• 块大小 $B = 6$，块数 $m = n/6 \approx 3.3 \times 10^4$
• 每个块计算 $(v, c)$ 需要 $O(B)$ 时间
• 线段树操作 $O(\log m)$
• 每次更新：$O(B + \log m)$
• 总复杂度：$O((n + q)(B + \log(n/B))) = O((n+q) \log n)$

---

五、算法正确性说明

1. 取整的正确性：递推中每一步取整不影响最终 $\lfloor f(n) \rfloor$，因为开方和加法在取整意义下可以交换顺序。

2. 块内二值性的正确性：由于 $B = 6$，前面值的影响最多让结果增加 $1$，因此每个块的输出只有 $v$ 或 $v+1$ 两种可能。

3. 合并规则的正确性：三种情况覆盖了 $v_1$ 与 $c_2$ 的所有大小关系，每种情况对应右块输出的确定值，同时正确传递了阈值信息。

4. 线段树的正确性：块的合并满足结合律，因此线段树可以正确维护整个序列的复合函数。

---

六、解题关键总结

步骤	关键点
数学观察	开方取整可下放；前面值影响范围 $\pm 1$
分块	块大小 $B = 6$，利用影响范围小的性质
块内处理	计算 $(v, c)$：$v$ 是零输入输出，$c$ 是增加 $1$ 的阈值
块间合并	三种情况合并两个 $(v, c)$，得到新的二元组
数据结构	线段树维护块序列，支持快速更新和查询
最终答案	查询整个序列，取 $v$ 值

---

七、算法扩展

除了线段树，也可以使用根号分治（块大小设为 $\sqrt{n}$ 或常数如 $100$），复杂度 $O(n + q\sqrt{n})$，在 $n, q \le 2 \times 10^5$ 时也能通过。