思路就是每个数最多被修改五次，由此来做分块。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,q;
int a[200005];
int tot[200005],l[200005],r[200005];
int ans[200005][6],cnt[200005];
void init()
{
    int len=sqrt(n);
    for(int i=1;i<=len;++i)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    if(len*len+1<=n)
    {
        l[len+1]=len*len+1;
        r[len+1]=n;
        len++;
    }
    for(int i=1;i<=len;++i)
    {
        for(int j=l[i];j<=r[i];++j)
        {
            int p=a[i];
            ans[i][0]+=a[i];
            for(int k=1;k<=5;++k)
            {
                p=sqrt(p);
                ans[i][k]+=p;
            }
        }
    }
}
void change(int x,int y)
{
    int p=tot[x],q=tot[y];
    if(p==q)
    {
        for(int i=x;i<=y;++i)
        {
        	int rr=cnt[p];
			int pqr=a[i];
			a[i]=sqrt(a[i]);
			for(int i=rr;i<=5;++i)
			{
				ans[p][i]-=pqr;
				pqr=sqrt(pqr);
				ans[p][i]+=pqr;
			} 
		} 
    }
    else
    {
    	for(int i=p+1;i<q;++i)
    	{
    		cnt[i]++;
    		if(cnt[i]>5)
    		cnt[i]--;
		}
		for(int i=x;i<=r[p];++i)
		{
			int rr=cnt[p];
			int pqr=a[i];
			a[i]=sqrt(a[i]);
			for(int j=rr;j<=5;++j)
			{
				ans[p][j]-=pqr;
				pqr=sqrt(pqr);
				ans[p][j]+=pqr;
			}
		}
		for(int i=l[q];i<=y;++i)
		{
			int rr=cnt[q];
			int pqr=a[i];
			a[i]=sqrt(a[i]);
			for(int j=rr;j<=5;++j)
			{
				ans[q][j]-=pqr;
				pqr=sqrt(pqr);
				ans[p][j]+=pqr;
			}
		}
	}
}
long long query(int x,int y)
{
	long long res=0;
	int p=tot[x],q=tot[y];
	if(p==q)
	{
		for(int i=x;i<=y;++i)
		{
			for(int j=1;j<=cnt[p];++j)
			{
				a[i]=sqrt(a[i]);
			}
			res+=a[i];
		}
	}
	else
	{
		for(int i=p+1;i<q;++i)
		{
			res+=ans[i][cnt[i]];
		}
		for(int i=x;i<=r[p];++i)
		{
			for(int j=1;j<=cnt[p];++j)
			{
				a[i]=sqrt(a[i]);
			}
			res+=a[i];
		}
		for(int i=l[q];i<=y;++i)
		{
			for(int j=1;j<=cnt[q];++j)
			{
				a[i]=sqrt(a[i]);
			}
			res+=a[i];
		}
	}
	return res;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    init();
    while(q--)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            printf("%lld\n",query(x,y));
        }
        else
        {
            change(x,y);
        }
    }
    return 0;
}