分块WA求条QWQ，P4145能过

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define L (in[r] - 1) * len + 1
#define R (in[l]) * len
inline int read(){
   int x = 0, f = 1; char c = getchar();
   while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar();}
   while(c >= '0' && c <= '9'){ x = x * 10 + c - '0' ;c = getchar();}
   return x * f;
}
const int N = 1e5 + 5;
int n, q;
int in[N], a[N], sum[N], lin[N], rin[N];
signed main()
{
	while(cin >> n) {

	int len = sqrt(n) + 1;
	for(int i = 1; i <= n; i ++) sum[i] = 0;
	for(int i = 1; i <= n; i ++) a[i] = read();
	for(int i = 1; i <= n; i ++) in[i] = (len + i - 1) / len;
	for(int i = 1; i <= in[n]; i ++) lin[i] = (i - 1) * len + 1, rin[i] = i * len;
	int q = read();
	rin[in[n]] = n;
	for(int i = 1; i <= n; i ++) sum[in[i]] += a[i];
	for(int i = 1; i <= q; i ++){
		int op = read(), l = read(), r = read();
		if(l > r) swap(l, r);
		if(!op){
			if(in[l] == in[r]){
				for(int i = l; i <= r; i ++){
					sum[in[i]] -= a[i];
					a[i] = sqrt(a[i]);
					sum[in[i]] += a[i];
				}
				continue;
			}
			for(int i = l; i <= R; i ++){
				sum[in[i]] -= a[i];
				a[i] = sqrt(a[i]);
				sum[in[i]] += a[i];
			}
			for(int i = L; i <= r; i ++){
				sum[in[i]] -= a[i];
				a[i] = sqrt(a[i]);
				sum[in[i]] += a[i];
			}
			for(int i = in[l] + 1; i < in[r]; i ++){
				if(sum[i] == len) continue;
				else{
					for(int j = lin[i]; j <= rin[i]; j ++){
						sum[in[j]] -= a[j];
						a[j] = sqrt(a[j]);
						sum[in[j]] += a[j];
					}
				}
			}
		}else{
			long long ans = 0;
			if(in[l] == in[r]){
				for(int i = l; i <= r; i ++) ans += a[i];
				printf("%lld\n", ans);
				continue;
			}
			for(int i = l; i <= R; i ++) ans += a[i];
			for(int i = L; i <= r; i ++) ans += a[i];
			for(int i = in[l] + 1; i < in[r]; i ++) ans += sum[i];
			printf("%lld\n", ans);
		}
	}
	
	
	}
	return 0;
}