首页 > 代码库 > BZOJ 3343：教主的魔法（分块）
BZOJ 3343：教主的魔法（分块）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3343
【题目大意】
给出一个数列，有区间加法操作，询问区间大于等于c的数字个数
【题解】
我们将数据分块，区间加法等价于各个块整块加法以及首位部分的个体加法，
由于要查询区间大于等于c的数字个数，
因此我们在每个块发生相对大小变动的时候对块内元素映射进行一次排序，
因为每次只有最左和最右的块相对大小发生变动，因此修改操作仍为O(sqrt(n))
查询时我们二分查找每个块中满足大小的个数，查询复杂度O(sqrt(n)log(sqrt(n)))
总复杂度O(qsqrt(n)log(sqrt(n))。
【代码】
#include <cstdio>#include <algorithm>#include <cmath>using namespace std;int n,m,q,block;const int N=1000010; int a[N],b[N],pos[N],add[N];void Sortblock(int x){ int l=(x-1)*block+1,r=min(x*block,n); for(int i=l;i<=r;i++)b[i]=a[i]; sort(b+l,b+r+1);}int find(int x,int v){ int l=(x-1)*block+1,r=min(x*block,n); int R=r; while(l<=r){ int mid=(l+r)>>1; if(b[mid]<v)l=mid+1; else r=mid-1; }return R-l+1;}void update(int x,int y,int v){ if(pos[x]==pos[y]){for(int i=x;i<=y;i++)a[i]+=v;} else{ for(int i=x;i<=pos[x]*block;i++)a[i]+=v; for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]+=v; }Sortblock(pos[x]);Sortblock(pos[y]); for(int i=pos[x]+1;i<pos[y];i++)add[i]+=v;}int query(int x,int y,int v){ int res=0; if(pos[x]==pos[y]){for(int i=x;i<=y;i++)if(a[i]+add[pos[i]]>=v)res++;} else{ for(int i=x;i<=pos[x]*block;i++)if(a[i]+add[pos[i]]>=v)res++; for(int i=(pos[y]-1)*block+1;i<=y;i++)if(a[i]+add[pos[i]]>=v)res++; }for(int i=pos[x]+1;i<pos[y];i++)res+=find(i,v-add[i]); return res;}int main(){ while(~scanf("%d%d",&n,&q)){ block=int(sqrt(n)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); pos[i]=(i-1)/block+1; b[i]=a[i]; } if(n%block)m=n/block+1; else m=n/block; for(int i=1;i<=m;i++)Sortblock(i); for(int i=1;i<=q;i++){ char op[5]; int x,y,v; scanf("%s%d%d%d",op,&x,&y,&v); if(op[0]==‘M‘)update(x,y,v); else printf("%d\n",query(x,y,v)); } }return 0;}BZOJ 3343：教主的魔法（分块）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。