我的思路就是把将每个节点开方 $i$ 次的和都存下来，$tab$ 表示当前节点被开方了多少次。

#include <bits/stdc++.h>
#define N 200006
using namespace std;
int n,m;
long long a[N][8],val[4*N][8],tab[4*N];
inline void pushdown(int p) {
	for (int i=0;i<=6;i++) {
		val[p<<1][i]=val[p<<1][min(7ll,i+tab[p])];
		val[p<<1^1][i]=val[p<<1^1][min(7ll,i+tab[p])];
//		printf("%d %d %lld\n",p,i,val[p<<1^1][i]); 
	}
	tab[p<<1]+=tab[p];
	tab[p<<1^1]+=tab[p];
	tab[p]=0;
	return;
}
inline void pushup(int p) {
	for (int i=0;i<=6;i++) val[p][i]=val[p<<1][i]+val[p<<1^1][i];
	return;
}
void build(int p,int l,int r) {
	if (l==r) {
		for (int i=0;i<=7;i++) {
			val[p][i]+=a[l][i];
//			printf("%d %d %d %lld\n",l,r,i,val[p][i]);
		}
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1^1,mid+1,r);
	pushup(p);
	return;
}
void upd(int p,int l,int r,int L,int R) {
	if (L<=l&&r<=R) {
//		printf("%d %d %lld\n",l,r,val[p][0]); 
		for (int i=0;i<=6;i++) {
			val[p][i]=val[p][i+1];
		}
		tab[p]++;
		return;
	}
	if (tab[p]&&l!=r) pushdown(p);
	int mid=(l+r)>>1;
	if (L<=mid) upd(p<<1,l,mid,L,R);
	if (R>mid) upd(p<<1^1,mid+1,r,L,R);
	pushup(p);
	return;
}
long long get(int p,int l,int r,int L,int R) {
	if (L<=l&&r<=R) {
		return val[p][0];
	}
	if (tab[p]&&l!=r) pushdown(p);
	int mid=(l+r)>>1;
	long long ans=0;
	if (L<=mid) ans+=get(p<<1,l,mid,L,R);
	if (R>mid) ans+=get(p<<1^1,mid+1,r,L,R);
	return ans;
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
    	scanf("%lld",&a[i][0]);
    	for (int j=1;j<=7;j++) {
    		a[i][j]=sqrt(a[i][j-1]);
//    		printf("%d %d %lld\n",i,j,a[i][j]);
		}
	}
    build(1,1,n);
    scanf("%d",&m);
    for (int i=1;i<=m;i++) {
    	int opt,l,r;
    	scanf("%d",&opt);
    	if (opt==2) {
    		scanf("%d %d",&l,&r);
    		if (l>r) swap(l,r);
    		upd(1,1,n,l,r);
		} else {
			scanf("%d %d",&l,&r);
			if (l>r) swap(l,r);
			printf("%lld\n",get(1,1,n,l,r));
		}
	}
    return 0;
}