提交记录

https://www.luogu.com.cn/record/173740924

预处理
ll n2[1000005];
void initN2() {for (int i = 1; i <= 1e6; i++) n2[i] = 1ll * i * i;}
然后一个arr[p]的sqrt等于
std::lower_bound(n2+1, n2+1000001, arr[p]+1) - n2 - 1

卡个常可以莽过去，但是加强版1e18就寄了

只用了树状数组和预处理所以这是一个水蓝（