分块
若块内最大值为0或1，则不用再开方
然后暴力修改
可以证明，如果开方后向下取整，则最多开方4次一个数就会变成0或1
#include#include #include #include using namespace std;long long n,sz,num,belong[50010],a[50010],maxb[50010],sum[50010];void calbe(int n){ for(int i=1;i<=n;i++) belong[i]=(i-1)/sz+1;}void reset(int x){ maxb[x]=0; sum[x]=0; for(int i=(x-1)*sz+1;i<=min(sz*x,n);i++){ maxb[x]=max(maxb[x],a[i]); sum[x]+=a[i]; }}long long query(int l,int r){ int xl=belong[l]; int xr=belong[r]; long long ans=0; for(int i=l;i<=min(xl*sz,(long long)r);i++) ans+=a[i]; if(xl!=xr){ for(int i=(xr-1)*sz+1;i<=r;i++) ans+=a[i]; } for(int i=xl+1;i<=xr-1;i++) ans+=sum[i]; return ans;}void update(int l,int r){ int xl=belong[l]; int xr=belong[r]; for(int i=l;i<=min(xl*sz,(long long)r);i++){ a[i]=sqrt(a[i]); } reset(xl); if(xl!=xr){ for(int i=(xr-1)*sz+1;i<=r;i++){ a[i]=sqrt(a[i]); } reset(xr); } for(int i=xl+1;i<=xr-1;i++){ if(maxb[i]<=1) continue; for(int j=(i-1)*sz+1;j<=i*sz;j++) a[j]=sqrt(a[j]); reset(i); }}int main(){ scanf("%lld",&n); sz=sqrt(n); num=n/sz; if(n%sz) num++; calbe(n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=num;i++) reset(i); for(int i=1;i<=n;i++){ int opt,l,r,c; scanf("%d %d %d %d",&opt,&l,&r,&c); if(opt==0) update(l,r); else printf("%lld\n",query(l,r)); } return 0;}