题目链接：https://loj.ac/problem/6281
参考博客：https://blog.csdn.net/qq_36038511/article/details/79725027
我一开始看到开方有点懵，看了上面的博客说2^31差不多5次开方就快变成1了，可以开标记数组，于是按照这个思路写了下，然后就过了，看来以后还要多看题意分析数据。
代码：
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 50010 int n,m,k,t,block; int a[maxn],tag[maxn],sum[maxn],vis[maxn],lump[maxn]; void kaif(int l,int r)//把l到r之间的数字开方 { for(int i=l;i<=min(lump[l]*block,r);i++)//直接改左边的不完整区间，同时该区间和 { sum[lump[l]]-=a[i]; a[i]=sqrt(a[i]); sum[lump[l]]+=a[i]; } if(lump[l]!=lump[r]) { for(int i=(lump[r]-1)*block+1;i<=r;i++) { sum[lump[r]]-=a[i]; a[i]=sqrt(a[i]); sum[lump[r]]+=a[i]; } } for(int i=lump[l]+1;i<=lump[r]-1;i++)//记录这个区间开方了多少次 { tag[i]++; } } int cal(int x,int num)//求数字x开方num次得出的结果 { while(num--&&x>1) { x=sqrt(x); } return x; } int get_sum(int l,int r)//求区间和 { int ans=0; for(int i=l;i<=min(lump[l]*block,r);i++)//左区间暴力求和 { ans+=cal(a[i],tag[lump[l]]); } if(lump[l]!=lump[r]) { for(int i=(lump[r]-1)*block+1;i<=r;i++)//右区间 { ans+=cal(a[i],tag[lump[r]]); } } for(int i=lump[l]+1;i<=lump[r]-1;i++) { if(!vis[i])//如果vis[i]==0,表示区间i还有大于1的数字 { int flag=0;//标记看开方之后是否还有大于1的数字 sum[i]=0;//区间和清空 for(int j=(i-1)*block+1;j<=i*block;j++) { a[j]=cal(a[j],tag[i]); sum[i]+=a[j];//重新计算区间和 if(a[j]>1)//只要有一个大于1 flag=1; } tag[i]=0;//区间未开方数字清零 if(!flag) vis[i]=1; } ans+=sum[i]; } return ans; } int main() { scanf("%d",&n); block=sqrt(n); fill(sum,sum+maxn-1,0); fill(tag,tag+maxn-1,0); fill(vis,vis+maxn-1,0); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); lump[i]=(i-1)/block+1; sum[lump[i]]+=a[i]; } for(int i=1;i<=n;i++) { int op,l,r,w; scanf("%d%d%d%d",&op,&l,&r,&w); if(op==0) kaif(l,r); else printf("%d ",get_sum(l,r)); } return 0; }