题解：花神游历各国

核心问题

维护一个数组，支持：

1. 查询区间和
2. 对区间内每个数开平方（下取整）

关键性质

• 对一个数 $a_i$ 不断开平方，只需 $O(\log \log a_i)$ 次就会变为 $1$
• 当 $a_i = 1$ 后，继续开平方还是 $1$，不再变化

数据结构选择

使用线段树维护：

• sum[num]：区间和
• maxi[num]：区间最大值

算法思路

1. 建树：

   • 递归建立线段树，每个叶子节点保存原始值
   • 内部节点保存子区间的和与最大值

2. 查询操作：

   • 标准线段树区间和查询

3. 修改操作（开平方）：

   • 如果当前节点区间最大值 $=1$，则无需修改（因为 $1$ 开平方仍为 $1$）
   • 否则，递归到叶子节点，直接对其开平方
   • 回溯时更新 sum 和 maxi

时间复杂度

• 查询：$O(\log n)$
• 修改：最坏 $O(n \log n)$，但利用“最大值 $=1$ 时剪枝”的优化，总复杂度接近 $O(n \log n \cdot \log \log \text{maxval})$，可以接受

代码要点

• 使用 maxi 数组判断是否需要继续递归
• 只在叶子节点进行实际的平方根计算
• 注意 int 转 long long 防止溢出
• 对于操作 2，若 $l > r$ 需要交换（题目可能隐含这个情况）

总结

本题巧妙利用了“多次开平方会迅速变为 $1$”的性质，在线段树中加入剪枝，避免了暴力修改导致的时间超限。是线段树优化区间修改的经典例题。