【题目大意】
给出一些数，有两种操作。(1)将区间内每一个数开方(2)查询每一段区间的和
【思路】
普通的线段树保留修改+开方优化。可以知道当一个数为0或1时，无论开方几次，答案仍然相同。所以设置flag=1。如果一个节点的左右孩子flag均为1，那么它的flag也是1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
using namespace std;
const int MAXN=+;
int n,m;
LL sum[MAXN<<];
int flag[MAXN<<]; void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
flag[rt]=flag[rt<<]&flag[rt<<|];
} void build(int l,int r,int rt)
{
flag[rt]=;
if (l==r)
{
scanf("%lld",&sum[rt]);
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
} void update(int L,int R,int l,int r,int rt)
{
if (flag[rt]) return;
if (l==r)
{
sum[rt]=(LL)sqrt(sum[rt]);
if (sum[rt]== || sum[rt]==) flag[rt]=;
return;
}
int m=(l+r)>>;
if (L<=m) update(L,R,lson);
if (R>m) update(L,R,rson);
pushup(rt);
} LL query(int L,int R,int l,int r,int rt)
{
if (L<=l && r<=R) return sum[rt];
int m=(l+r)>>;
LL ret=;
if (L<=m) ret+=query(L,R,lson);
if (R>m) ret+=query(L,R,rson);
return ret;
} int main()
{
scanf("%d",&n);
build(,n,);
scanf("%d",&m);
for (int i=;i<m;i++)
{
int x,l,r;
scanf("%d%d%d",&x,&l,&r);
if (x==) printf("%lld\n",query(l,r,,n,));
else update(l,r,,n,);
}
return ;
}