传送门：LOJ#6281. 数列分块入门 5
题意：给出一个长为n的数列，以及n个操作，操作涉及区间开方，区间求和。
对于区间开方，对于整个块似乎不能进行操作。所以得对整个块进行暴力修改。
这个算法优化的关键点就是无论哪个数经过多次开方都会变成0或1，这样的话再怎么开方，块内的这些数都不会怎么改变.我们可以对块内元素经过修改是否都变为0或1进行标记，如果整个块都变为0或1，那么再对块进行修改时就可忽略。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=5e4+10;
typedef long long ll;
ll a[maxn],n,block,pos[maxn],sum[maxn];
bool flag[maxn];void solve_sqrt(ll x){if(flag[x]) return ;flag[x]=true;sum[x]=0;for(int i=(x-1)*block+1;i<=x*block;i++){a[i]=sqrt(a[i]);sum[x]+=a[i];if(a[i]>1) flag[x]=false;}}void add(ll l,ll r){for(ll i=l;i<=min(pos[l]*block,r);i++){if(flag[pos[l]]) break;sum[pos[i]]-=a[i];a[i]=sqrt(a[i]);sum[pos[i]]+=a[i];}if(pos[l]!=pos[r]){for(ll i=(pos[r]-1)*block+1;i<=r;i++){if(flag[pos[r]]) break;sum[pos[i]]-=a[i];a[i]=sqrt(a[i]);sum[pos[i]]+=a[i];}}for(ll i=pos[l]+1;i<pos[r];i++){solve_sqrt(i);}}ll query(ll l,ll r){ll ans=0;for(ll i=l;i<=min(pos[l]*block,r);i++){ans+=a[i];}if(pos[l]!=pos[r]){for(ll i=(pos[r]-1)*block+1;i<=r;i++){ans+=a[i];}}for(ll i=pos[l]+1;i<pos[r];i++){ans+=sum[i];}return ans;}int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}block=sqrt(n);for(ll i=1;i<=n;i++){pos[i]=(i-1)/block+1;sum[pos[i]]+=a[i];}ll opt,l,r,c;for(int i=0;i<n;i++){scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);if(opt==0) add(l,r);else printf("%lld\n",query(l,r));}return 0;
}