BZOJ原题地址

洛谷原题地址

题面

写一个支持区间开方区间求和的数据结构。

思路

我不会支持区间开方的数据结构,所以我选择暴力单点修改,树状数组区间查询。

因为1e12的数开方6次就变成了1,所以需要修改的次数实际上很少,用并查集可以跳过小于等于1的数,然后。。。树状数组单点修改即可。没开O2,最慢的点大概就是250ms,还是比较快的。

代码

非常短。。。

树状数组两行搞定,并查集一行搞定。

修改的时候判断一下是不是小于等于1,是的话就更新一下fa数组,具体看一下注释。