zkw线段树的发明人，【codevs2492】【Tyvj1941】上帝造题的七分钟2，线段树的特别技巧

传送门1
传送门2
写在前面：现在要干的事情更多了
思路：开方这玩意好像没法加lazy，只能暴力向下找，但是我们可以想到当有一段全是1的时候这一段一定不用再修改了，所以我们加一个判断这段区间是否全为1的标记，这样就能大大减少复杂度了，剩下就是狂敲代码了
注意：LL
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m;
LL a[100002];
struct os
{LL sum;bool f;
}tree[400002];
void build(int now,int begin,int end)
{if (begin==end) {tree[now].sum=a[end];return;}int mid=(begin+end)>>1;build(now<<1,begin,mid);build(now<<1|1,mid+1,end);tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}
void update(int now,int begin,int end,int l,int r)
{if (tree[now].f) return;if (begin==end){tree[now].sum=sqrt(tree[now].sum);if (tree[now].sum<=1) tree[now].f=1;return;}int mid=(begin+end)>>1;if (mid>=l) update(now<<1,begin,mid,l,r);if (mid<r) update(now<<1|1,mid+1,end,l,r);tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;tree[now].f=tree[now<<1].f&tree[now<<1|1].f;
}
LL get(int now,int begin,int end,int l,int r)
{if (l<=begin&&end<=r) return tree[now].sum;LL ans=0;int mid=(begin+end)>>1;if (mid>=l) ans+=get(now<<1,begin,mid,l,r);if (mid<r) ans+=get(now<<1|1,mid+1,end,l,r);return ans;
}
main()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,1,n);scanf("%d",&m);int opt,x,y;while (m--){scanf("%d%d%d",&opt,&x,&y);if (x>y) swap(x,y);if (opt) printf("%lld\n",get(1,1,n,x,y));else update(1,1,n,x,y);}
}