传送门
解题思路
和这个题几乎一样。
这里是开方，比取模进行次数更少。次数k大约为 (log_2(log_2n))。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,m;
struct node{
long long max,sum;
}d[maxn*4];
inline void pushup(int id){
d[id].max=max(d[id*2].max,d[id*2+1].max);
d[id].sum=d[id*2].sum+d[id*2+1].sum;
}
void update(int id,int l,int r,int x,long long v){
if(l==r){
d[id].sum=d[id].max=v;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(id*2,l,mid,x,v);
else update(id*2+1,mid+1,r,x,v);
pushup(id);
}
long long query(int id,int l,int r,int x,int y){
if(x<=l&&r<=y){
return d[id].sum;
}
int mid=(l+r)/2;
long long res=0;
if(x<=mid) res+=query(id*2,l,mid,x,y);
if(y>mid) res+=query(id*2+1,mid+1,r,x,y);
return res;
}
void update_sqrt(int id,int l,int r,int x,int y){
if(d[id].max<=1) return;
if(l==r){
d[id].sum=d[id].max=sqrt(d[id].sum);
return;
}
int mid=(l+r)/2;
if(x<=mid&&d[id*2].max>1) update_sqrt(id*2,l,mid,x,y);
if(y>mid&&d[id*2+1].max>1) update_sqrt(id*2+1,mid+1,r,x,y);
pushup(id);
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
long long a;
cin>>a;
update(1,1,n,i,a);
}
cin>>m;
for(int i=1;i<=m;i++){
int tp,l,r;
cin>>tp>>l>>r;
if(l>r) swap(l,r);
if(tp==1) cout<<query(1,1,n,l,r)<<endl;
else update_sqrt(1,1,n,l,r);
}
return 0;
}