[UOJ228]基础数据结构练习题(线段树)

发布于 2018-05-07  163 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[UOJ228]基础数据结构练习题(线段树)

Description

sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧。
在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。
给出一个长度为 nn 的数列 AA,接下来有 mm 次操作,操作有三种:
对于所有的 i∈[l,r]i∈[l,r],将 AiAi 变成 Ai+xAi+x。
对于所有的 i∈[l,r]i∈[l,r],将 AiAi 变成 ⌊Ai‾‾√⌋⌊Ai⌋。
对于所有的 i∈[l,r]i∈[l,r],询问 AiAi 的和。
作为一个不怎么熟练的初学者,sylvia 想了好久都没做出来。而可怜酱又外出旅游去了,一时间联系不上。于是她决定向你寻求帮助:你能帮她解决这个问题吗。

Tag

线段树

解决思路

区间开根不满足加和性,所以只能暴力下放。
考虑有那些时候是可以简化开根操作的。首先,若区间内所有数都小于等于1,则不需要向下操作了。
其次,不断地开根会使得数值范围越来越小,那么若区间最大值与区间最小值开根后的结果相等,那么直接区间覆盖。
最后,当最大值$max-\sqrt{max}$与最小值$min-\sqrt{min}$相同,则打区间减法标记。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[UOJ228]基础数据结构练习题(线段树)


HNCJ OIer