#6281. 数列分块入门 5
题目：
简要题意：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间开方，区间求和。
题解：
怎么说...这道题loj的数据有点水。
和bzoj花神游历各国是一样的...但是loj没有卡掉不完全优化的代码。
基础操作就不说了（同分块4），主要讲优化吧：
不难发现，因为开方后我们是向下取整的，那么如果一直开方下去，整个序列一定会变成0或1。那么如果当前区间都是0或1就没有操作的必要了嘛。
讲到这里思路就已经很清晰了，但是一开始的时候本蒟蒻并没有优化头尾的块，依然在loj AC了...bzoj就挂了，事实证明：暴力加优化才是分块真正的难点！
代码：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 LL n,m,a[110000],sum[110000]; 9 LL block,pos[110000];10 bool v[110000];11 void reset(LL x)12 {13 if(v[x])return ;14 v[x]=1;sum[x]=0;15 for(int i=(x-1)*block+1;i<=x*block;i++)16 {17 a[i]=sqrt(a[i]);sum[x]+=a[i];18 if(a[i]>1)v[x]=0;19 }20 }21 void update(LL l,LL r)22 {23 if(!v[pos[l]])24 {25 for(int i=l;i<=min(pos[l]*block,r);i++)26 {27 sum[pos[l]]-=a[i];28 a[i]=sqrt(a[i]);29 sum[pos[l]]+=a[i];30 }31 v[pos[l]]=1;for(int i=(pos[l]-1)*block+1;i<=pos[l]*block;i++)if(a[i]>1)v[pos[l]]=0;32 }33 if(pos[l]!=pos[r])34 {35 if(!v[pos[r]])36 {37 for(int i=(pos[r]-1)*block+1;i<=r;i++)38 {39 sum[pos[r]]-=a[i];40 a[i]=sqrt(a[i]);41 sum[pos[r]]+=a[i];42 }43 v[pos[r]]=1;for(int i=(pos[r]-1)*block;i<=pos[r]*block;i++)if(a[i]>1)v[pos[r]]=0;44 }45 }46 for(int i=pos[l]+1;i<=pos[r]-1;i++)reset(i);47 }48 void sol(LL l,LL r)49 {50 LL ans=0;51 for(int i=l;i<=min(pos[l]*block,r);i++)ans+=a[i];52 if(pos[l]!=pos[r])53 for(int i=(pos[r]-1)*block+1;i<=r;i++)54 ans+=a[i];55 for(int i=pos[l]+1;i<=pos[r]-1;i++)ans+=sum[i];56 printf("%lld\n",ans);57 }58 int main()59 {60 memset(v,false,sizeof(v));61 scanf("%lld",&n);62 for(int i=1;i<=n;i++)scanf("%lld",&a[i]);63 block=sqrt(n);64 for(int i=1;i<=n;i++)65 {66 pos[i]=(i-1)/block+1;67 sum[pos[i]]+=a[i];68 }69 for(int i=1;i<=n;i++)70 {71 LL opt,l,r,c;scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);72 if(opt==0)update(l,r);73 else sol(l,r);74 }75 return 0;76 }