区间开方，求和。

分析性质可发现sqrt（0）= 0，sqrt(1) = 1，所以记录每块是否已不能改变。

区分l与r啊。。错了这么个关键字母可不爆零了么。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 ll bl[50050],fns[250],v[50050],sum[250];
10 ll n,blo,c,l,r,opt;
11 
12 void check(ll x){
13     for(register int i = (x-1)*blo+1;i <= min(n,x*blo);i++)
14         if(v[i]^0&&v[i]^1)return;
15     fns[x] = 1;
16 }
17 
18 void change(ll l,ll r){
19     ll x,flag;
20     if(bl[l] == bl[r]){
21         flag = true;
22         for(register int i = l;i <= r;i++)if(v[i] > 1){
23             x = sqrt(v[i]);
24             sum[bl[l]] -= v[i]-x;
25             v[i] = x;
26             if(x > 1)flag = false;
27         } if(flag)check(bl[l]); return;
28     }
29     if(!fns[bl[l]]){
30         flag = true;
31         for(register int i = l;i <= bl[l]*blo;i++)if(v[i] > 1){
32             x = sqrt(v[i]);
33             sum[bl[l]] -= v[i]-x;
34             v[i] = x;
35             if(x > 1)flag = false;
36         } if(flag)check(bl[l]);
37     }
38     if(!fns[bl[r]]){
39         flag = true;
40         for(register int i = (bl[r]-1)*blo+1;i <= r;i++)if(v[i] > 1){
41             x = sqrt(v[i]);
42             sum[bl[r]] -= v[i]-x;
43             v[i] = x;
44             if(x > 1)flag = false;
45         } if(flag)check(bl[r]);
46     }
47     for(register int i = bl[l]+1;i < bl[r];i++)if(!fns[i]){
48         flag = true;
49         for(register int j = (i-1)*blo+1;j <= min(n,i*blo);j++)if(v[j] > 1){
50             x = sqrt(v[j]);
51             sum[i] -= v[j]-x;
52             v[j] = x;
53             if(x > 1)flag = false;
54         } if(flag)check(i);
55     }
56 }
57 
58 ll query(ll l,ll r){
59     ll ans = 0;
60     if(bl[l] == bl[r]){
61         for(register int i = l;i <= r;i++)ans += v[i];
62         return ans;
63     }
64     for(register int i = l;i <= bl[l]*blo;i++)ans += v[i];
65     for(register int i = (bl[r]-1)*blo+1;i <= r;i++)ans += v[i];
66     for(register int i = bl[l]+1;i < bl[r];i++)ans += sum[i];
67     return ans;
68 }
69 
70 int main(){
71     scanf("%lld",&n); blo = sqrt(n);
72     for(register int i = 1;i <= n;i++){
73         scanf("%lld",&v[i]);
74         bl[i] = (i-1)/blo+1;
75         sum[bl[i]] += v[i];
76     }
77     for(register int i = 1;i <= bl[n];i++)check(i);
78     for(register int i = 1;i <= n;i++){
79         scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);
80         switch(opt){
81             case 0:change(l,r);break;
82             case 1:printf("%lld\n",query(l,r));break;
83         }
84     }    
85 return 0;
86 }