传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3211
【题解】
区间开根号，由于每个数被开根号不会很多次就变成1，每次我们暴力开根下去，同时记录s[x]表示x这个区间内是不是全是1，如果是就不用开下去了
这样保证了每个数最多被开不多次。
# include <math.h> # include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h>using namespace std;typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7;# define RG register # define ST staticint n; int seq[M];ll w[M]; bool s[M]; inline void build(int x, int l, int r) {s[x] = 0; if(l == r) {w[x] = seq[l];return ;}int mid = l+r>>1;build(x<<1, l, mid);build(x<<1|1, mid+1, r);w[x] = w[x<<1] + w[x<<1|1]; }inline void change(int x, int l, int r, int L, int R) {if(s[x]) return; if(l == r) {w[x] = sqrt(w[x]);if(w[x] <= 1) s[x] = 1; return ;}int mid = l+r>>1;if(R <= mid) change(x<<1, l, mid, L, R); else if(L > mid) change(x<<1|1, mid+1, r, L, R);else change(x<<1, l, mid, L, mid), change(x<<1|1, mid+1, r, mid+1, R);w[x] = w[x<<1] + w[x<<1|1];s[x] = s[x<<1] & s[x<<1|1]; }inline ll query(int x, int l, int r, int L, int R) {if(L <= l && r <= R) return w[x];int mid = l+r>>1;if(R <= mid) return query(x<<1, l, mid, L, R);else if(L > mid) return query(x<<1|1, mid+1, r, L, R);else return query(x<<1, l, mid, L, mid) + query(x<<1|1, mid+1, r, mid+1, R); }int main() {scanf("%d", &n); for (int i=1; i<=n; ++i) scanf("%d", seq+i); build(1, 1, n);int q; scanf("%d", &q);while(q--) {int opt, l, r;scanf("%d%d%d", &opt, &l, &r); if(l>r) swap(l, r); if(opt == 1) {printf("%lld\n", query(1, 1, n, l, r));} else change(1, 1, n, l, r);}return 0; }
