首页 > 代码库 > 刷题向》关于线段树的区间开根号 BZOJ3211
刷题向》关于线段树的区间开根号 BZOJ3211
这是一道关于线段树的区间开根号的裸题，没什么好讲的。
值得注意的是，因为有区间开根号的性质，所以我们每一次更改操作只能把更改区间所覆盖的所有元素全部查找，当然你直接找效率明显爆炸。。。
能够注意到，指数级别的操作一次更改的数字都很大，而题目的数字最大是10的9次，所以可以注意到的是当一个区间更新6遍以后就失去更新的意义了，因为当你更改次数超过6次所有非负整数数字就全部会化为1。所以可以在每一个节点上加一个类似于LAZY标记的东西，记录开根号次数，以便节约跟新时间。
贴出题目&代码
Description
线段树区间开根号与求和
Input
第一行N代表有N个数
第二行有N个数，代表这N个值分别是多少
第三行有一个M
接下来M行，每行有X,L,R
当X为1代表求区间：（L,R）的和。
当X为2代表对区间：（L,R）开根号。
Output
每次x=1时，每行一个整数，表示区间和
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9
刷题向》关于线段树的区间开根号 BZOJ3211
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。