论分块为什么是那啥

众所周知，$10^{12}$ 顶多开 $6$ 次平方变为 $1$，而 $1$ 开多少次平方都是 $1$.
所以我们可以利用这一点来做
用一个lazytag来记录一个块现在需要开几次根，如果全变为 $1$ 就变成 $-1$，这样就能用 $O(1)$ 时间遍历这个块了
剩下的自己看代码

//开6次根 
#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
int a[100005];
int lazytag[405];
int len, n, m, tmp, l, r;
int _sqrt(int n){
	return (n == 1 ? 1 : sqrt(n));
}
void modify(int l, int r){
	if(r - l < len){
		for(int i = l; i <= r; i++){
			a[i] = _sqrt(a[i]);
		}
		return;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		if(lazytag[i] == -1 || ++lazytag[i] >= 6) lazytag[i] = -1;
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		a[i] = _sqrt(a[i]);
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		a[i] = _sqrt(a[i]);
	}
}
int query(int l, int r){
	int ct = 0;
	if(r - l < len){
		for(int i = l; i <= r; i++){
			if(lazytag[i / len] == -1){
				ct++;
				continue;
			}
			int tmp = a[i];
			for(int j = 1; j <= lazytag[i / len]; j++) tmp = _sqrt(tmp);
			ct += tmp;
		}
		return ct;
	}
	for(int i = l / len + 1; i < r / len; i++){//整块 
		if(lazytag[i] == -1){
			ct += len;
			continue;
		}
		bool flag = 1;
		for(int j = i * len; j < (i + 1) * len; j++){
			for(int k = 1; k <= lazytag[i]; k++){//唯一一次敢开三重循环的（
				a[j] = _sqrt(a[j]);
			}
			ct += a[j];
			if(a[j] != 1) flag = 0;
		}
		lazytag[i] = (flag ? -1 : 0);
	}
	for(int i = l; i < min(r + 1, (l / len + 1) * len); i++){//散块 
		if(lazytag[i / len] == -1){
			ct++;
			continue;
		}
		int tmp = a[i];
		for(int j = 1; j <= lazytag[i / len]; j++) tmp = _sqrt(tmp);
		ct += tmp;
	}
	for(int i = max(r / len * len, l + 1); i <= r; i++){
		if(lazytag[i / len] == -1){
			ct++;
			continue;
		}
		int tmp = a[i];
		for(int j = 1; j <= lazytag[i / len]; j++) tmp = _sqrt(tmp);
		ct += tmp;
	}
	return ct;
}
signed main(){
	cin >> n;
	len = sqrt(n);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	cin >> m;
	while(m--){
		cin >> tmp >> l >> r;
		if(l > r) swap(l, r);
		if(tmp) cout << query(l, r) << endl;
		else modify(l, r);
	}

	return 0;
}

单次询问时间复杂度最高为 $O(n)$，但所有查询的时间复杂度还是为 $O(6\times n+\sqrt n)$.