线段树维护区间和与最值，利用平方根快速收敛剪枝区间开方。
OJ: luogu
题目 ID: P4145
难度:提高
标签:线段树区间开方剪枝python
日期: 2026-07-16 23:59
题意
对区间每个数做一次向下取整平方根，或查询区间和。
思路
数值为 1 时再开方不会改变。节点维护区间和、最小值、最大值：若整段 min == max，可以直接把整段赋成 isqrt(value)；若 max <= 1，直接剪枝。否则递归到相交子区间。平方根操作会让大数迅速下降，均摊访问量可控。
Python 知识
math.isqrt是整数平方根，避免浮点精度问题。- 赋值懒标记用
0表示“没有标记”，因为题目中的数始终为正。 max <= 1的提前return是这类势能下降操作的关键优化。
代码
python
import sys
from array import array
from math import isqrt
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n = int(input())
values = array("q", map(int, input().split()))
operations = int(input())
total = array("q", [0]) * (4 * n)
minimum = array("q", [0]) * (4 * n)
maximum = array("q", [0]) * (4 * n)
assigned = array("q", [0]) * (4 * n)
def apply(node, value, length):
total[node] = value * length
minimum[node] = maximum[node] = value
assigned[node] = value
def build(node, left, right):
if left == right:
total[node] = minimum[node] = maximum[node] = values[left - 1]
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
pull(node)
def pull(node):
left, right = node * 2, node * 2 + 1
total[node] = total[left] + total[right]
minimum[node] = min(minimum[left], minimum[right])
maximum[node] = max(maximum[left], maximum[right])
def push(node, left, right):
if assigned[node] and left != right:
middle = (left + right) // 2
apply(node * 2, assigned[node], middle - left + 1)
apply(node * 2 + 1, assigned[node], right - middle)
assigned[node] = 0
def update(node, left, right, query_left, query_right):
if query_right < left or right < query_left or maximum[node] <= 1:
return
if query_left <= left and right <= query_right and minimum[node] == maximum[node]:
apply(node, isqrt(maximum[node]), right - left + 1)
return
push(node, left, right)
middle = (left + right) // 2
if query_left <= middle:
update(node * 2, left, middle, query_left, query_right)
if middle < query_right:
update(node * 2 + 1, middle + 1, right, query_left, query_right)
pull(node)
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return total[node]
push(node, left, right)
middle = (left + right) // 2
answer = 0
if query_left <= middle:
answer += query(node * 2, left, middle, query_left, query_right)
if middle < query_right:
answer += query(node * 2 + 1, middle + 1, right, query_left, query_right)
return answer
build(1, 1, n)
answers = []
for _ in range(operations):
kind, left, right = map(int, input().split())
if left > right:
left, right = right, left
if kind:
answers.append(str(query(1, 1, n, left, right)))
else:
update(1, 1, n, left, right)
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-16 23:46
* update_at: 2026-07-16 23:46
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
建树 O(n)；单次操作为线段树访问并带平方根收敛剪枝，空间 O(n)。
总结
当区间修改会快速降低数值时，维护最值并在“整段相同”时批量处理，通常比强行维护复杂懒标记更简单。