链接：https://vjudge.net/contest/260644#problem/H
思路：我们考虑1e18内的数据可以在常数次以内开根号变为1，所以我们维护区间信息时考虑维护区间最大值，如果区间最大值为1的话那么当前区间所有值都为1不用再递归，否则递归左右子树一直到叶节点或者到区间最大值为1的地方，在叶节点更新值，同时pushup回去合并区间信息。注意本题有些很无聊的坑点，输入需要特判一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int maxv[maxn<<2];
long long sum[maxn<<2],a[maxn];
int n,q;
inline void pushup(int o){
sum[o] = sum[o<<1] + sum[o<<1|1];
maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
}
void build(int o,int l,int r){
if(l<r){
int mid = l+r>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
else{
sum[o] = a[l];
maxv[o] = a[l];
}
}
void update(int o,int tl,int tr,int l,int r){
if(tr<l||r<tl)return;
if(maxv[o]==1){
return;
}
if(tr==tl){
a[tl] = (int)sqrt(a[tl]+0.5);
maxv[o] = a[tl];
sum[o] = a[tl];
return;
}
int mid = (tl+tr)>>1;
update(o<<1,tl,mid,l,r);
update(o<<1|1,mid+1,tr,l,r);
pushup(o);
}
long long query(int o,int tl,int tr,int l,int r){
if(tr<l||r<tl)return 0;
if(l<=tl&&r>=tr)return sum[o];
//pushdown(o,tr-tl+1);
int mid = (tl+tr)>>1;
long long ret = query(o<<1,tl,mid,l,r);
ret+=query(o<<1|1,mid+1,tr,l,r);
return ret;
}
int main(){
int kase = 0;
while(~scanf("%d",&n)){
printf("Case #%d:\n",++kase);
memset(maxv,0,sizeof(maxv));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
int d,e,f;
scanf("%d%d%d",&d,&e,&f);
if(e>f)swap(e,f);//特判一下
if(d)printf("%lld\n",query(1,1,n,e,f));
else update(1,1,n,e,f);
}
printf("\n");
}
return 0;
}
