代码应该还是比较清晰的。 思想就是暴力单点修改+区间查询。

#include <iostream>
#include <stdio.h>
#define mid ((l+r)>>1)
#define ll long long
using namespace std;
const int N=1e5+5;
int n;
ll a[N],sum[N+N+N],maxn[N+N+N];

inline ll my_sqrt(ll x);
inline void init(int id,int l,int r);
inline void pushup(int id);
inline void change(int id,int l,int r,int x,int y);
inline ll getsum(int id,int l,int r,int x,int y);

signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	init(1,1,n);
	int op,x,y,test_times;scanf("%d",&test_times);
	while(test_times--){
		scanf("%d %d %d",&op,&x,&y);
		if(op) printf("%lld\n",getsum(1,1,n,x,y));
		else change(1,1,n,x,y);
	}
	return 0;
}

inline ll my_sqrt(ll x){
	ll l=1,r=1000000,ans=1;
	while(l<=r){
		if(mid*mid<=x) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
inline void init(int id,int l,int r){
	if(l>r) return;
	if(l==r){
		sum[id]=maxn[id]=a[l];
		return;
	}
	init(id<<1,l,mid);init(id<<1|1,mid+1,r);
	pushup(id);
	return;
}
inline void pushup(int id){
	sum[id]=sum[id<<1]+sum[id<<1|1];
	maxn[id]=max(maxn[id<<1],maxn[id<<1|1]);
}
inline void change(int id,int l,int r,int x,int y){
	if(l>r||y<l||x>r) return;
	if(maxn[id]<2) return;
	if(l==r){sum[id]=maxn[id]=my_sqrt(sum[id]);return;}
	if(maxn[id<<1]>=2&&x<=mid&&y>=l) change(id<<1,l,mid,x,y);
	if(maxn[id<<1|1]>=2&&x<=r&&y>=mid+1) change(id<<1|1,mid+1,r,x,y);
	pushup(id);
}
inline ll getsum(int id,int l,int r,int x,int y){
	if(l>r) return 0ll;
	if(x<=l && r<=y) return sum[id];
	ll ans1=0ll,ans2=0ll;
	if(x<=mid) ans1=getsum(id<<1,l,mid,x,y);
	if(y>mid) ans2=getsum(id<<1|1,mid+1,r,x,y);
	return ans1+ans2;
}