难度： 蓝

算法： 线段树，分块等

线段树我不太会，所以我使用分块做法。

第一次写分块，写的不好请见谅。

发现一个性质：一个数操作 $6$ 次后就会变成 $1$，然后无论继续进行多少次操作，这个数还是 $1$。

那么我们分块维护每个数操作 $k$ 次后的值以及每一块操作 $k$ 次的值。因为上面的性质所以有 $k\le 6$。

分块实现过程：

对于单点修改，直接修改这个点值，然后更新该点所在块总和。需要修改对该点以及所在块操作 $0,1,2,3,4,5$ 次的值。

对于整块修改，记录每个块修改次数，给该块修改次数 $+1$。但注意其不能大于 $6$。

对于单点查询，查询该点操作 $k$ 次的值。$k$ 为该点所在块修改次数。

对于整块查询，查询该块操作 $k$ 次的值。$k$ 为该块修改次数。

以上所有操作都可以在 $O(k\sqrt n)$ 内完成，$k=6$。总时间复杂度 $O(mk\sqrt n)$，最慢的点跑了 $711$ms，硬生生的卡了过去。

代码如下，如果上面看不懂可以参考：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,q,ans,p[101000][10],f[500][10],k[500],e[500],d[101000],x,l,r,u,w;
//p[][i]为该数修改i次后的值 f[][i]为该块修改i次后的值 k[]为块的修改次数 e[]为该块起点 d[]为每个点所属块 
int main(){
	scanf("%lld",&n);
	m=sqrt(n);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&p[i][0]);
		for(ll j=1;j<=6;j++) p[i][j]=sqrt(p[i][j-1]);
	}
	for(ll i=1;i<=n;i++){
		d[i]=(i+m-1)/m;
		if(e[(i+m-1)/m]==0) e[(i+m-1)/m]=i;
	} 
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<=6;j++){
			f[d[i]][j]+=p[i][j];
		}
	}
	scanf("%lld",&q);
	while(q--){
		scanf("%lld%lld%lld",&x,&l,&r);
		if(x==2){
			for(ll i=l;i<=r;){
				u=d[i];
				if(e[u+1]<=r&&e[u+1]>0&&(d[i]!=d[i-1]||i==1)){
					k[u]=min(k[u]+1,6ll);
					i=e[u+1];
				}
				else{
					for(int j=0;j<=5;j++){
						f[u][j]=(f[u][j]-p[i][j]+p[i][j+1]);
						p[i][j]=p[i][j+1];
					}
					i++;
				}
			}
		}
		else{
			ans=0;
			for(ll i=l;i<=r;){
				u=d[i],w=k[u];
				if(e[u+1]<=r&&e[u+1]>0&&(d[i]!=d[i-1]||i==1)){
					ans+=f[u][w];
					i=e[u+1];
				}
				else{
					ans+=p[i][w];
					i++;
				}
			}
			printf("%lld\n",ans);
		}
	}
}