题解：P13980 数列分块入门 5
wht_1218
·
·
题解
通过测试，不超过 5 次开方可以使数字为 1 或者 0。对 0 或 1 开根是“无效”的。
所以我们可以暴力地对 \ge1 的数开方。
考虑如何用分块求解。
分成 \frac n T 块，每块的长度最多为 T。
对于修改，一定会包含至少 1 个块。
- 暴力处理第一个块和最后一个块（也就是部分包含的块）。
- 中间的完整的块中，若所有数均是“无效”的，则不处理该块，否则暴力处理。
对于查询，一定会包含至少 1 个块。
- 暴力对第一个块和最后一个块求和。
- 对于中间的完整的块，在修改和预处理时统计块内之和即可。
此时总时间复杂度 $O(n\sqrt n)$。
```cpp
csti N=3e5+7;
int n,T,a[N],L[N],R[N],pos[N];
int val[N],sum[N];
bool tag[N];
il void solve(csti x){
if(tag[x])return;
sum[x]=0,tag[x]=true;
cst int RR=R[x];
rep(i,L[x],RR){
if(val[i]){
val[i]=sqrt(val[i]),sum[x]+=val[i];
if(tag[x]&&val[i]>1)tag[x]=false;
}
}
}
il void add(csti l,csti r,csti v){
csti Pl=pos[l],Pr=pos[r],R1=min(R[Pl],r),R2=Pr-1;
rep(i,l,R1){
if(val[i])sum[Pl]-=val[i],val[i]=sqrt(val[i]),sum[Pl]+=val[i];
}
if(Pl^Pr){
rep(i,L[Pr],r){
if(val[i])sum[Pr]-=val[i],val[i]=sqrt(val[i]),sum[Pr]+=val[i];
}
}
rep(i,Pl+1,R2){
solve(i);
}
return;
}
il int query(csti l,csti r){
int ans=0;
csti Pl=pos[l],Pr=pos[r],R1=min(R[Pl],r),R2=Pr-1;
rep(i,l,R1){
ans+=val[i];
}
if(Pl^Pr){
rep(i,L[Pr],r){
ans+=val[i];
}
}
rep(i,Pl+1,R2){
ans+=sum[i];
}
return ans;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n,T=pow(n,0.5);
rep(i,1,n)cin>>a[i],L[i]=(i-1)*T+1,R[i]=i*T,pos[i]=(i-1)/T+1,sum[pos[i]]+=a[i],val[i]=a[i];
rep(i,1,n){
int op,l,r,c;cin>>op>>l>>r;
if(op&1){
cout<<query(l,r)<<'\n';
}else{
add(l,r,c);
}
}
return 0;
}
```