询问区间和都好说。但是开方？？
其实是这样的，一个数（1e9）以内连续开方6次就会变成1，于是我们就可在开方操作上进行暴力修改。暴力修改的意思其实也就是找到叶子节点进行修改，一步一步向上反，也就把区间操作解决了。
为了防止发生区间已经都为1了我们还傻傻开方的情况，可以再维护一个区间内最大值元素。以免我们办傻事。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 100090 using namespace std;
typedef long long ll; int n,m,cnt;
ll a[maxn];
struct SegmentTree{
int l,r;
ll sum,val;
}t[*maxn]; void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].sum=t[p].val=a[l];
return ;
}
int mid=(l+r)>>;
build(p*,l,mid);
build(p*+,mid+,r);
t[p].sum=t[p*].sum+t[p*+].sum;
t[p].val=max(t[p*].val,t[p*+].val);
} void change(int p,int l,int r)
{
if(t[p].l==t[p].r)
{
t[p].sum=sqrt(t[p].sum);
t[p].val=sqrt(t[p].val);
return ;
}
int mid=(t[p].l+t[p].r)>>;
if(l<=mid&&t[p*].val>) change(p*,l,r);
if(r>mid&&t[p*+].val>) change(p*+,l,r);
t[p].sum=t[p*].sum+t[p*+].sum;
t[p].val=max(t[p*].val,t[p*+].val);
} ll ask(int p,int l,int r)
{
if(t[p].l==l&&t[p].r==r) return t[p].sum;
int mid=(t[p].l+t[p].r)>>;
if(l>mid) return ask(p*+,l,r);
else if(r<=mid) return ask(p*,l,r);
else return ask(p*,l,mid)+ask(p*+,mid+,r);
} int main()
{
while(scanf("%d",&n)!=EOF)
{
printf("Case #%d:\n",++cnt);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
build(,,n);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
int opt=,l=,r=;
scanf("%d%d%d",&opt,&l,&r);
if(l>r) swap(l,r);
if(opt==)
printf("%lld\n",ask(,l,r));
else if(opt==)
change(,l,r);
}
memset(t,,sizeof(t));
}
return ;
}
SPOJ GSS4