C++分块入门

分块是一种类似线段树的算法便于区间、单点加法区间、单点求值。比如有一组元素A :123256579。把它3个一块123 256 579。假设要将第2个数到第7个数都加2。我们发现第2块的数都要加2我们不妨建一个数组tagtag[k]表示第k块整体加的数。原数组A变成145 256 779 tag[2]2边角不成整块的直接在原数组上加成整块的在tag上标记。如果要我们求第5个数第五个数属于第二块用A[5]tag[2]即可。那么几个元素一块最好呢设n个元素B个一块每次加法要执行Bn/B次操作要使这个值最小B要等于根号n所以这段程序的时间复杂度为O(根号n*操作次数)。例题n个元素n此操作n50000每次操作输入opt,l,r,c。若 opt0表示将位于 [l,r] 的之间的数字都加 c。若 opt1表示询问第r个数的值l 和 c 忽略。#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] void init(){ Bsqrt(n)1; tot(nB-1)/B;//向上取整 for(int k1;ktot;k){ //L[1]1,R[1]B //L[2]B1,R[2]2B //... L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){//l,r都在一整块 for(int il;ir;i)a[i]c; return; } for(int il;iR[lb];i)a[i]c;//左边角料 ,无法打标记 for(int iL[rb];ir;i)a[i]c;//右边角料 ,无法打标记 for(int klb1;krb-1;k)tag[k]c;//中间整块部分 } ll query(int r){//查询 return a[r]tag[bel[r]]; } int main(){ cinn; init(); for(int i1;in;i)cina[i]; for(int i1;in;i){ int op,l,r; ll c; cinoplrc; if(!op)add(l,r,c); else coutquery(r)endl; } return 0; }区间加法区间求和#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] ll sum[N];//sum[k]表示原数组第k块的和 void init(){ Bsqrt(n)1; tot(nB-1)/B; for(int k1;ktot;k){ L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){ for(int il;ir;i){ a[i]c; sum[lb]c; } return; } for(int il;iR[lb];i){ a[i]c; sum[lb]c; } for(int iL[rb];ir;i){ a[i]c; sum[rb]c; } for(int klb1;krb-1;k){ tag[k]c; } } __int128 query(int l,int r,int c){ int lbbel[l],rbbel[r]; __int128 ans0; if(lbrb){ for(int il;ir;i)ansansa[i]tag[lb]; return ans; } for(int il;iR[lb];i)ansansa[i]tag[lb]; for(int iL[rb];ir;i)ansansa[i]tag[rb]; for(int klb1;krb-1;k)anssum[k](__int128)tag[k]*(R[k]-L[k]1); return ans; } int main(){ cinn; init(); for(int i1;in;i){ cina[i]; sum[bel[i]]a[i]; } for(int i1;in;i){ int op,l,r; ll c; cinoplrc; modc1; if(!op)add(l,r,c); else cout(ll)(((query(l,r,c)%mod)mod)%mod)endl; } return 0; }求区间内小余c平方的个数这是分块经典例题维护数组v也是B个元素一块每块内的元素时刻与原数组对应但不同的是对于块内元素是单调递增的。在查询的时候暴力查询边角元素不成整块查询整块时用二分查询v数组对应块中小余c*c-tag[k]的元素。#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] ll v[N]; void resort(int k){//维护v数组 for(int iL[k];iR[k];i)v[i]a[i]; sort(vL[k],vR[k]1); } void init(){ Bsqrt(n)1; tot(nB-1)/B; for(int k1;ktot;k){ L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){ for(int il;ir;i)a[i]c; resort(lb); return; } for(int il;iR[lb];i)a[i]c; for(int iL[rb];ir;i)a[i]c; resort(lb); resort(rb); for(int klb1;krb-1;k)tag[k]c; } int count_less_block(int k,ll x){//二分查询v数组块内小余x-tag[k]的个数 ll needx-tag[k]; return lower_bound(vL[k],vR[k]1,need)-(vL[k]); } ll query(int l,int r,ll x){ int lbbel[l],rbbel[r]; int ans0; if(lbrb){ for(int il;ir;i){ if(a[i]tag[lb]x)ans; } return ans; } //暴力查询不成块的元素 for(int il;iR[lb];i){ if(a[i]tag[lb]x)ans; } for(int iL[rb];ir;i){ if(a[i]tag[rb]x)ans; } for(int klb1;krb-1;k)anscount_less_block(k,x); return ans; } int main(){ cinn; init(); for(int i1;in;i)cina[i]; for(int k1;ktot;k)resort(k); for(int i1;in;i){ int op,l,r; ll c; cinoplrc; if(!op)add(l,r,c); else coutquery(l,r,c*c)endl; } return 0; }谢谢观看。