上帝造题的七分钟2/花神游历各国/GSS4 线段树维护区间开方 By cellur925
询问区间和都好说。但是开方？？
其实是这样的，一个数（1e9）以内连续开方6次就会变成1，于是我们就可在开方操作上进行暴力修改。暴力修改的意思其实也就是找到叶子节点进行修改，一步一步向上反，也就把区间操作解决了。
为了防止发生区间已经都为1了我们还傻傻开方的情况，可以再维护一个区间内最大值元素。以免我们办傻事。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #define maxn 100090 6 7 using namespace std; 8 typedef long long ll; 9 10 int n,m,cnt; 11 ll a[maxn]; 12 struct SegmentTree{ 13 int l,r; 14 ll sum,val; 15 }t[4*maxn]; 16 17 void build(int p,int l,int r) 18 { 19 t[p].l=l,t[p].r=r; 20 if(l==r) 21 { 22 t[p].sum=t[p].val=a[l]; 23 return ; 24 } 25 int mid=(l+r)>>1; 26 build(p*2,l,mid); 27 build(p*2+1,mid+1,r); 28 t[p].sum=t[p*2].sum+t[p*2+1].sum; 29 t[p].val=max(t[p*2].val,t[p*2+1].val); 30 } 31 32 void change(int p,int l,int r) 33 { 34 if(t[p].l==t[p].r) 35 { 36 t[p].sum=sqrt(t[p].sum); 37 t[p].val=sqrt(t[p].val); 38 return ; 39 } 40 int mid=(t[p].l+t[p].r)>>1; 41 if(l<=mid&&t[p*2].val>1) change(p*2,l,r); 42 if(r>mid&&t[p*2+1].val>1) change(p*2+1,l,r); 43 t[p].sum=t[p*2].sum+t[p*2+1].sum; 44 t[p].val=max(t[p*2].val,t[p*2+1].val); 45 } 46 47 ll ask(int p,int l,int r) 48 { 49 if(t[p].l==l&&t[p].r==r) return t[p].sum; 50 int mid=(t[p].l+t[p].r)>>1; 51 if(l>mid) return ask(p*2+1,l,r); 52 else if(r<=mid) return ask(p*2,l,r); 53 else return ask(p*2,l,mid)+ask(p*2+1,mid+1,r); 54 } 55 56 int main() 57 { 58 while(scanf("%d",&n)!=EOF) 59 { 60 printf("Case #%d: ",++cnt); 61 for(int i=1;i<=n;i++) 62 scanf("%lld",&a[i]); 63 build(1,1,n); 64 scanf("%d",&m); 65 for(int i=1;i<=m;i++) 66 { 67 int opt=0,l=0,r=0; 68 scanf("%d%d%d",&opt,&l,&r); 69 if(l>r) swap(l,r); 70 if(opt==1) 71 printf("%lld ",ask(1,l,r)); 72 else if(opt==0) 73 change(1,l,r); 74 } 75 memset(t,0,sizeof(t)); 76 } 77 return 0; 78 }