标签:数据结构-线段树

这似乎是个很经典的题,但因为我很菜所以现在才做。显然,一个 $\le 10^{5}$ 的数最多经过 $6$ 次开方就一定可以变成 $1$ ,所以我们可以用线段树对每次询问进行单点修改,如果区间最大值 $\le 1$ 就不需要进行修改了。这样最多每个数修改 $6$ 次,查询直接区间查询,总时间复杂度是 $O(n\times \log n + 6n)$ 。struct Tree{ ll ...
题解 数据结构-线段树
提高+/省选-