对于 100\%100% 的数据, 1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}1≤n≤50000,?231≤others,\mathrm{ans} \leq 2^{31}-1ans≤231?1.
思路: 这题棘手的地方在与块中开方的处理, 怎么处理呢? 一个区间里每一个数的开方, 这个要想不遍历一遍很难, 但是遍历的话还要分块干嘛呢? 问题就在开方这个字眼, 题目中给的范围里的数,
假设最大 2^32 最多开方 6 次就变为 0 或者 1 了 一个数变为 0 或者 1 他再开方就不会再变化了, 试想一下, 假如一个区间里所有的数都变为了 0 或者 1 那么还要处理吗 显然是不用的, 所以我们就记录哪些区间
里的所有的数都变为了 0 或者 1 是的话就不用处理这个块了, 这就是分块在这里的巧妙之处了!!! 下面看代码:
- #include<iostream>
- #include<string.h>
- #include<math.h>
- using namespace std;
- const int maxn=50000+5;
- int a[maxn];
- int block;
- int bl[maxn];
- int sum[maxn];
- int flag[maxn];
- void Updata_bl(int x)
- {
- if(flag[x]) return ;
- flag[x]=1;
- sum[x]=0;
- for(int i=(x-1)*block+1;i<=x*block;i++)
- {
- a[i]=sqrt(a[i]);
- sum[x]+=a[i];
- if(a[i]>1) flag[x]=0;
- }
- }
- void Updata(int l,int r)
- {
- for(int i=l;i<=min(bl[l]*block,r);i++)
- {
- sum[bl[i]]-=a[i];
- a[i]=sqrt(a[i]);
- sum[bl[i]]+=a[i];
- }
- if(bl[l]!=bl[r])
- {
- for(int i=(bl[r]-1)*block+1;i<=r;i++)
- {
- sum[bl[r]]-=a[i];
- a[i]=sqrt(a[i]);
- sum[bl[r]]+=a[i];
- }
- }
- for(int i=bl[l]+1;i<=bl[r]-1;i++)
- {
- Updata_bl(i);
- }
- }
- void Query(int l,int r)
- {
- int ans=0;
- for(int i=l;i<=min(bl[l]*block,r);i++) ans+=a[i];
- if(bl[l]!=bl[r])
- {
- for(int i=(bl[r]-1)*block+1;i<=r;i++) ans+=a[i];
- }
- for(int i=bl[l]+1;i<=bl[r]-1;i++) ans+=sum[i];
- cout<<ans<<endl;
- }
- int main()
- {
- int n;
- int opt,l,r,c;
- cin>>n ;
- memset(sum,0,sizeof(sum));
- memset(flag,0,sizeof(flag));
- block=sqrt(n);
- for(int i=1;i<=n;i++) cin>>a[i];
- for(int i=1;i<=n;i++)
- {
- bl[i]=(i-1)/block+1;
- sum[bl[i]]+=a[i];
- }
- for(int i=1;i<=n;i++)
- {
- cin>>opt>>l>>r>>c;
- if(opt==0) Updata(l,r);
- else Query(l,r);
- }
- }
来源: http://www.bubuko.com/infodetail-2935900.html