线段树
区间开方线段树
其实也可以分块写
不管数有多大，那么开方若干次后一定是0/1，这时就无需继续开方，有一个tag标记维护即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; typedef ll arr[400002]; template <typename T> inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); } int n,m; arr sum,tag; inline void build(int o,int l,int r){ if(l==r) {read(sum[o]); return;} int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); build(lc,l,mid); build(rc,mid+1,r); sum[o]=sum[lc]+sum[rc]; } int x1,x2; inline void _sqrt(int o,int l,int r){ if(tag[o]) return ; if(l==r){ sum[o]=sqrt(sum[o]); if(sum[o]<2) tag[o]=1; return; } int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); if(x1<=mid) _sqrt(lc,l,mid); if(x2>mid) _sqrt(rc,mid+1,r); sum[o]=sum[lc]+sum[rc]; tag[o]=tag[lc]&tag[rc]; //如果本区间都无需开方 } inline ll query(int o,int l,int r){ if(x1<=l&&r<=x2) return sum[o]; ll ans=0; int lc=o<<1,rc=o<<1|1,mid=l+((r-l)>>1); if(x1<=mid) ans+=query(lc,l,mid); if(x2>mid) ans+=query(rc,mid+1,r); return ans; } int main(){ read(n); build(1,1,n); read(m); int opt; for(int i=1;i<=m;++i){ read(opt); read(x1); read(x2); if(x1>x2) swap(x1,x2); if(opt==0) _sqrt(1,1,n); else printf("%lld ",query(1,1,n)); }return 0; }