rt，下面的代码使用链表维护不为 $1$ 的数的位置，最坏情况下时间复杂度为 $O(n^2)$：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
#define next _next
inline char gtc(){
	static char tmp[1<<20],*p=0,*top=0;
	if(p==top){
		p=tmp;
		top=tmp+fread(tmp,1,1<<20,stdin);
		if(p==top)return EOF;
	}
	return *p++;
}
#define getchar gtc
inline void read(int &x){
	static char c;
	while((c=getchar())<'0');
	x=c^'0';
	while((c=getchar())>='0')x=(x<<3)+(x<<1)+(c^'0');
}
inline void read(long long &x){
	static char c;
	while((c=getchar())<'0');
	x=c^'0';
	while((c=getchar())>='0')x=(x<<3)+(x<<1)+(c^'0');
}
#define int long long
#define N 100001
long long a[N],c[N];
#define lowbit(x) (x&((~x)+1))
inline void change(int x,const int& n){
	long long k=sqrtl(a[x]),h;
	h=a[x]-k;
	a[x]=k;
	while(x<=n){
		c[x]-=h;
		x+=lowbit(x);
	}
}
inline long long cha(int l,int r){
	if(r==0)return 0;
	if(l==1){
		int ans=0;
		while(r){
			ans+=c[r];
			r-=lowbit(r);
		}
		return ans;
	}
	return cha(1,r)-cha(1,l-1);
}
signed next[N],list[N],pre[N];
inline void del(const int& x){
	next[pre[x]]=next[x];
	pre[next[x]]=pre[x];
}
signed main(){
	int n,m,top=0;
	read(n);
	for(int i=1;i<=n;i++){
		int j=i;
		read(a[i]);
		while(j<=n){
			c[j]+=a[i];
			j+=lowbit(j);
		}
		if(a[i]>1){
			list[++top]=i;
			pre[top]=top-1;
			next[top]=top+1;
		}
	}
	pre[1]=next[top]=0;
	read(m);
	int k,l,r;
	signed first=1;
	while(m--){
		read(k);
		read(l);
		read(r);
		if(l>r)swap(l,r);
		if(k==0){
			for(int i=first;(list[i]<=r)&&i;i=next[i]){
				if(list[i]<l)continue;
				change(list[i],n);
				if(a[list[i]]==1){
					del(i);
					if(i==first)first=next[i];
				}
			}
		}
		else {
			printf("%lld\n",cha(l,r));
		}
	}
	return 0;
}

但实际上很轻松就能通过此题：评测记录

建议添加 hack 数据，我能想到的一种卡法：

100000
<随便 100000 个范围内的数>
100000
0 99999 100000
0 99999 100000
0 99999 100000
...
0 99999 100000
1 1 100000