#6281. 数列分块入门 5 – 题目 – LibreOJ (loj.ac)
区间开方，区间求和题。
显然，针对区间维护开方操作很难做到，于是考虑其值的性质，显然，int范围内的值最多开方6次就会变为1，之后再开方依然为1，于是考虑暴力维护一个区间内的值是否全部为1即可，全部为1标记上之后再遇到O(1)处理即可。复杂度大概就为O(n*6+n*sqrt(n))
代码如下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1e5)+5; int a[maxn]; int sum[maxn]; int bel[maxn]; int L[maxn],R[maxn]; bool tag[maxn]; void build(int n){ int block=sqrt(n); int num=n/block; if(n%block)num++; for(int i=1;i<=num;i++){ L[i]=(i-1)*block+1; R[i]=i*block; for(int j=L[i];j<=R[i];j++){ bel[j]=i; sum[i]+=a[j]; } } } void update(int l,int r){ if(bel[l]==bel[r]){ for(int i=l;i<=r;i++){ if(tag[bel[i]])break; sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i])); a[i]=int(sqrt(a[i])); } } else{ for(int i=l;i<=R[bel[l]];i++){ if(tag[bel[i]])break; sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i])); a[i]=int(sqrt(a[i])); } for(int i=L[bel[r]];i<=r;i++){ if(tag[bel[i]])break; sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i])); a[i]=int(sqrt(a[i])); } for(int i=bel[l]+1;i<bel[r];i++){ bool fg=1; for(int j=L[i];j<=R[i];j++){ if(tag[i])break; sum[i]=sum[i]-a[j]+int(sqrt(a[j])); a[j]=int(sqrt(a[j])); if(a[j]>1)fg=0; } if(fg)tag[i]=1; } } } void calc(int l,int r){ int ans=0; if(bel[l]==bel[r]){ for(int i=l;i<=r;i++){ ans+=a[i]; } } else{ for(int i=l;i<=R[bel[l]];i++){ ans+=a[i]; } for(int i=L[bel[r]];i<=r;i++){ ans+=a[i]; } for(int i=bel[l]+1;i<bel[r];i++){ ans+=sum[i]; } } cout<<ans<<endl; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; build(n); for(int i=1;i<=n;i++){ int opt,l,r,c; cin>>opt>>l>>r>>c; if(opt){ calc(l,r); } else{ update(l,r); } } return 0; }
#6283. 数列分块入门 7 – 题目 – LibreOJ (loj.ac)
区间乘法，区间加法，单点询问
类似线段树的实现操作，注意标记先乘后加。当时我调bug花了很久，主要原因是在处理离散块的时候我直接对a数组进行了修改操作，导致标记数组出错，解决方法为直接对离散块所属的完整块进行下放标记的操作（暴力但是可行）
代码如下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1e5)+5; const int modd=(1e4)+7; int a[maxn]; int bel[maxn]; int L[maxn],R[maxn]; int tag1[maxn]; int tag2[maxn]; void build(int n){ int block=sqrt(n); int num=n/block; if(n%block)num++; for(int i=1;i<=num;i++){ L[i]=(i-1)*block+1; R[i]=min(n,i*block); tag1[i]=0; tag2[i]=1; for(int j=L[i];j<=R[i];j++){ bel[j]=i; } } } void pushdown(int p){ int l=L[bel[p]],r=R[bel[p]]; for(int i=l;i<=r;i++){ a[i]=(a[i]*tag2[bel[p]]+tag1[bel[p]])%modd; } tag1[bel[p]]=0; tag2[bel[p]]=1; } void add(int l,int r,int c){ if(bel[l]==bel[r]){ pushdown(l); for(int i=l;i<=r;i++){ a[i]=(a[i]+c)%modd; } } else{ pushdown(l); for(int i=l;i<=R[bel[l]];i++){ a[i]=(a[i]+c)%modd; } pushdown(r); for(int i=L[bel[r]];i<=r;i++){ a[i]=(a[i]+c)%modd; } for(int i=bel[l]+1;i<bel[r];i++){ tag1[i]=(tag1[i]+c)%modd; } } } void multiply(int l,int r,int c){ if(bel[l]==bel[r]){ pushdown(l); for(int i=l;i<=r;i++){ a[i]=(a[i]*c)%modd; } } else{ pushdown(l); for(int i=l;i<=R[bel[l]];i++){ a[i]=(a[i]*c)%modd; } pushdown(r); for(int i=L[bel[r]];i<=r;i++){ a[i]=(a[i]*c)%modd; } for(int i=bel[l]+1;i<bel[r];i++){ tag1[i]=(tag1[i]*c)%modd; tag2[i]=(tag2[i]*c)%modd; } } } void calc(int i){ int ans=(a[i]*tag2[bel[i]]+tag1[bel[i]])%modd; cout<<ans<<endl; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; build(n); for(int i=1;i<=n;i++){ int opt,l,r,c; cin>>opt>>l>>r>>c; if(opt==0){ add(l,r,c); } if(opt==1){ multiply(l,r,c); } if(opt==2){ calc(r); } } return 0; }
#6284. 数列分块入门 8 – 题目 – LibreOJ (loj.ac)
区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。
这题我折腾了挺久。思路为标记每个区间是否为同一个值，若是则标记为该值，否则标记为1e11。之后在分块的模板中再分三种情况进行分析。1.该区间全部为c，2.该区间全部为另外一个值，3.该区间的值不统一。注意点：在离散块情况2进行修改操作时需要先进行标记下放操作，否则修改之后标记被覆盖为1e11。
代码如下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1e5)+5; ll a[maxn]; ll tag[maxn]; ll bel[maxn]; ll L[maxn],R[maxn]; void build(ll n){ ll block=sqrt(n); ll num=n/block; if(n%block)num++; for(int i=1;i<=num;i++){ L[i]=(i-1)*block+1; R[i]=min(n,i*block); tag[i]=1e11; for(int j=L[i];j<=R[i];j++){ bel[j]=i; } } } void pushdown(int p){ for(int i=L[p];i<=R[p];i++){ a[i]=tag[p]; } } void ope(ll l,ll r,ll c){ ll ans=0; if(bel[l]==bel[r]){ if(tag[bel[l]]==c){ ans+=r-l+1; } else if(tag[bel[l]]!=1e11){ pushdown(bel[l]); for(int i=l;i<=r;i++){ a[i]=c; } tag[bel[l]]=1e11; } else{ for(int i=l;i<=r;i++){ if(a[i]==c)ans++; else a[i]=c; } } } else{ if(tag[bel[l]]==c){ ans+=R[bel[l]]-l+1; } else if(tag[bel[l]]!=1e11){ pushdown(bel[l]); for(int i=l;i<=R[bel[l]];i++){ a[i]=c; } tag[bel[l]]=1e11; } else{ for(int i=l;i<=R[bel[l]];i++){ if(a[i]==c)ans++; else a[i]=c; } } if(tag[bel[r]]==c){ ans+=r-L[bel[r]]+1; } else if(tag[bel[r]]!=1e11){ pushdown(bel[r]); for(int i=L[bel[r]];i<=r;i++){ a[i]=c; } tag[bel[r]]=1e11; } else{ for(int i=L[bel[r]];i<=r;i++){ if(a[i]==c)ans++; else a[i]=c; } } for(int i=bel[l]+1;i<bel[r];i++){ if(tag[i]==c){ ans+=(R[i]-L[i]+1); } else if(tag[i]==1e11){ for(int j=L[i];j<=R[i];j++){ if(a[j]==c)ans++; else a[j]=c; } tag[i]=c; } else{ tag[i]=c; } } } cout<<ans<<endl; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; build(n); for(int i=1;i<=n;i++){ ll l,r,c; cin>>l>>r>>c; ope(l,r,c); } return 0; }
原文地址：http://www.cnblogs.com/yokino/p/16906210.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
