题目分析

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，需要处理 $n$ 次操作，操作分为两种类型：

操作 1：将区间 $[l, r]$ 内的每个元素 $a_i$ 替换为 $\lfloor \sqrt{a_i} \rfloor$（向下取整）

操作 2：查询区间 $[l, r]$ 内所有元素的和

算法思路

解决本题的核心在于认识到一个重要的数学性质：任何正整数经过有限次开方后都会收敛到 1。具体来说：

数字 $0$ 和 $1$ 开方后保持不变

对于 $a_i > 1$，经过有限次开方（大约 $O(\log \log a_i)$ 次）后就会变成 $1$

这意味着每个元素最多被"有效"开方有限次，之后再次开方不会改变其值。

分块算法设计

我们采用分块算法，并利用上述性质进行优化：

分块策略：

将数组分成 $\sqrt{n}$ 个块

每个块的大小约为 $\sqrt{n}$

数据结构：

arr：存储原始数组

block_sum：存储每个块的和

block_all_one：标记块是否全为 $0$ 或 $1$（无需再开方）

核心优化：

对于已标记为全 $0$ 或 $1$ 的块，跳过开方操作

每次开方操作后重新检查块的状态

算法复杂度分析

时间复杂度

区间开方：

最坏情况：$O(\sqrt{n})$ 每次操作

均摊情况：由于每个元素最多被有效开方有限次，总体复杂度为 $O(n\sqrt{n})$

区间求和：$O(\sqrt{n})$ 每次操作

空间复杂度

$O(n)$：存储数组和块的相关信息

优化效果 通过 block_all_one 标记的优化，算法在实际运行中表现出色：

减少不必要的计算：跳过已收敛的块

利用数学性质：基于开方操作的收敛特性

平衡复杂度：在预处理和查询之间取得良好平衡

代码总结

本题展示了如何利用数学性质来优化数据结构操作。分块算法结合开方操作的收敛特性，通过简单的标记优化，显著提高了算法效率。这种"有限次有效操作+标记优化"的思路可以应用于其他具有类似性质的问题。