luogu4145题解

传送门

一道线段树的题,并不是很复杂。

我们需要维护一个正整数数列,有区间和查询和区间开平方修改。

我们发现一个很好的特性:(sqrt 1 = 1)

所以我们可以维护一下区间最大值,如果不大于1那么就不需要进行任何修改,如果有大于1的就像左右递归,到树叶处手动修改。

我们算一下复杂度:一共n个数,每个数最多经历m次开方操作,这个m显然很小,所以复杂度正确可行

原文地址:https://www.cnblogs.com/nao-nao/p/13627565.html