BISHI127 区间根号与区间求和
中等通过率 41.92%python3样例通过牛客 AC
牛客原题 源码
讲解章节：树状数组与线段树
解题思路
这题考什么
势能分析 + 并查集跳跃，是「单次最坏 O(n)、但总量有界」的经典模型。
关键观察：开根收敛极快。
1e7 -> 3162 -> 56 -> 7 -> 2 -> 1 -> 1 -> ...
任何数最多开 6 次根就落到 <= 1，之后再开根不变。
所以「区间开根」的总单点修改次数是 O(6n)，而不是 O(qn)。
剩下的问题是「怎么跳过已经稳定（<= 1）的位置」——用并查集：
稳定一个就把它并到 i+1，之后所有查询自动跳过。
区间和为什么用分块而不是树状数组
两者都能做「单点改 + 区间查」，但代价结构正好相反：
树状数组：单点改 O(log n) = 17 步 Python 循环，区间查 2 * 17 步
分块： 单点改 O(1)（改 a[i] 和所属块的和），区间查 O(sqrt n)
——而且查询那一步是 sum(切片)，**整段跑在 C 层**
本题的修改次数（6e5）远多于查询次数（1e5），
所以要把成本压到修改这一侧：分块的单点改只有两条赋值语句，
而树状数组要走 17 步纯 Python 循环，两者差了一个数量级。
n = q = 1e5 的最坏数据实测：树状数组版 0.56 秒，分块版 0.35 秒。
注意 0.56 秒并不安全：判题机的机器通常比本机慢数倍，
本地耗时要留出 3~4 倍余量再去对照时限，
否则「本地看着够快」和「判题机上超时」完全可以同时成立。
数据规模与复杂度
n, q <= 1e5，a_i <= 1e7。块长取 B = 320（约 sqrt(n)）。
开根总次数 <= 6n = 6e5，每次 O(1)；
查询每次至多扫 2B 个元素 + n/B 个块和，都由 C 层的 sum 完成。
坑在哪
- 必须用 math.isqrt，不能用 int(x ** 0.5)：
后者在 1e7 附近可能因浮点误差差 1；
（注意 isqrt 是 3.8+ 才有的，牛客的 PyPy3 比 3.8 老，没有这个函数，
所以这题只能用 Python3 交，不能退化到 PyPy3。）
- 判「稳定」的条件是 <= 1（0 和 1 开根都是自己），不是 == 1；
- 2026-01-21 题面更新后 a_i >= 0，不必讨论负数开根；
- 并查集的 find 用迭代 + 路径减半，别写递归（深度可到 1e5）；
- 查询要分「同块」与「跨块」两种情形：同块时直接 sum(a[l:r+1])，
跨块才是「左残块 + 中间整块的块和 + 右残块」，
写成统一形式会在 kl == kr 时把中间那段算重。
参考实现
| solutions/BISHI127.py |
|---|
| import sys
from math import isqrt
B = 320 # 块长，约 sqrt(n)
def main() -> None:
# 输入最多 3e5 个整数，一次性读入再切分，比逐行 readline 快一个数量级
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [int(v) for v in data[2:2 + n]] # 这里用 0 下标，块号 = i // B
# 分块预处理：把数组切成 nb 个长为 B 的块，bsum[k] 是第 k 块的元素和。
# 之后单点修改只需同时改 a[i] 和 bsum[i // B]，两条赋值语句。
nb = (n + B - 1) // B
bsum = [sum(a[k * B:(k + 1) * B]) for k in range(nb)] # 末块通常不满，切片会自动截断
# 并查集初始化：nxt[i] 指向 i 右边第一个还没稳定的位置。
# 多开一格到 n 作哨兵，find 走到 n 就表示「右边全稳定了」，不必额外判越界。
nxt = list(range(n + 1)) # 并查集：右边第一个 a > 1 的位置
for i in range(n):
if a[i] <= 1: # 0 和 1 开根还是自己，一开始就摘出去
nxt[i] = i + 1
def find(x):
"""返回 x 自身或它右边第一个尚未稳定（a > 1）的位置。"""
while nxt[x] != x:
nxt[x] = nxt[nxt[x]] # 路径减半
x = nxt[x]
return x
p = 2 + n # 操作段在 data 里的起始位置
out = []
push = out.append # 绑定成局部名，省掉循环里每次的属性查找
for _ in range(q):
op = data[p] # 保持 bytes 原样比较，省一次 int() 转换
l = int(data[p + 1]) - 1 # 题面下标从 1 起，这里统一减 1 转成 0 下标
r = int(data[p + 2]) - 1
p += 3
if op == b"1": # 区间开根：只碰还没稳定的位置
i = find(l) # 从 l 起第一个 a > 1 的位置开始
# 每个数最多被开 6 次根就落到 <= 1，所以这个循环全程总共只转 O(6n) 次
while i <= r:
old = a[i]
new = isqrt(old)
a[i] = new
bsum[i // B] += new - old # 单点改块和，O(1)
if new <= 1: # 稳定了，从并查集里摘掉
nxt[i] = i + 1
i = find(i + 1) # 跳到下一个未稳定位置，跳过的都是死值
else: # 区间求和
kl = l // B # 左端点所在块
kr = r // B # 右端点所在块
if kl == kr: # 同块，直接扫这一段
push(sum(a[l:r + 1]))
else: # 左残块 + 中间整块 + 右残块
push(sum(a[l:(kl + 1) * B])
+ sum(bsum[kl + 1:kr])
+ sum(a[kr * B:r + 1]))
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
|