```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+25;
int n,a[N],pos[N],L[N],R[N],sum[N],flag[N];
void calc(int p){
if(flag[p])return;
flag[p]=1;
sum[p]=0;
int cnt=0;
for(int i=L[p];i<=R[p];i++){
if(!a[i])++cnt;
}
if(cnt==R[p]-L[p]+1)return;
for(int i=L[p];i<=R[p];i++){
a[i]=(int)sqrt(a[i]);
sum[p]+=a[i];
if(a[i]>1)
flag[p]=0;
}
}
void modify(int l,int r){
int ans=0;
int p=pos[l],q=pos[r];
if(p==q)for(int i=l;i<=r;i++)
sum[p]-=a[i],a[i]=sqrt(a[i]),sum[p]+=a[i];
else{
for(int i=l;i<=R[p];i++)
sum[p]-=a[i],a[i]=sqrt(a[i]),sum[p]+=a[i];
for(int i=L[q];i<=r;i++)
sum[q]-=a[i],a[i]=sqrt(a[i]),sum[q]+=a[i];
for(int i=p+1;i<=q-1;i++)calc(i);
}
}
int query(int l,int r){
int ans=0;
int p=pos[l],q=pos[r];
if(p==q){
for(int i=l;i<=r;i++)
ans+=a[i];
}
else{
for(int i=l;i<=R[p];i++)
ans+=a[i];
for(int i=L[q];i<=r;i++)
ans+=a[i];
for(int i=p+1;i<=q-1;i++)
ans+=sum[i];
}
return ans;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int t=sqrt(n);
for(int i=1;i<=t;i++)
L[i]=(i-1)*t+1,R[i]=i*t;
R[t]=n;
for(int i=1;i<=t;i++)
for(int j=L[i];j<=R[i];j++)
pos[j]=i,sum[i]+=a[j];
int opt,l,r,c,m;
cin>>m;
for(int i=1;i<=m;i++){
cin>>opt>>l>>r;
if(!opt)modify(l,r);
else cout<<query(l,r)<<endl;
}
return 0;
}
```
50pts了
by 114514xxx @ 2024-08-15 11:09:57
@[114514xxx](/user/749175) 能发一下提交记录或测试点情况吗
by pengbonan @ 2024-08-15 11:10:19
@[pengbonan](/user/1005693) [提交记录](https://www.luogu.com.cn/record/172763636)
by 114514xxx @ 2024-08-15 11:44:30
@[114514xxx](/user/749175) 建议把块长和块的数量分开
by pengbonan @ 2024-08-15 13:55:15