首先，我们知道，分块是一种优雅的暴力，他可以很灵活的变通，下面，我整理了几道分块的经典题目跟大家分享（持续更新中）：
1.区间加，区间求小于 k 的数的个数。
这是分块里比较经典的一道题目了。首先看区间加，我们把序列分成 n/S 个块（S为块长），对每个不完整的块（角块），直接暴力加，因为块长为 S,所以这里的复杂度是 O(S)，不会太大，然后我们把每个完整的区间，打上一个tag，这个tag里边记录的是这个整块一共加了多少，这样，复杂度最坏就是 O(n/S),为了均衡，所以一般我们的块长取 √n。
再就是区间求小于个数，一开始我们肯定没啥想法，但是大家肯定都用过二分吧，在本来有序的序列里边，我们可以二分查找一下这个个数，这样就可以做到log的时间复杂度求出整块小于 k 的个数了。但是好像直接二分似乎麻烦了一些，这时候就可以请出万能的STL的。
在STL库的vector中，我们可以这样查找小于 k 的数的个数
vector<int>v; //do something... v.lower_bound(v.begin(),v.end(),k)
这里边用到了一个东西叫lower_bound,这是个好东西，可以在log时间复杂度内求区间小于 k 的数的个数，所以我们就想，是不是也可以将每个块放进这样一个vector里边，对每个块进行排序（复杂度O(nlogn)）,然后还是那个思路，角块直接暴力统计，对于每个完整的块，用lower_bound二分一下（k-这块的tag）这个值，就可以在单次 O(S*logS) 的复杂度内求出小于 k 的个数。
所以我们不得不感叹，STL大法好\(^o^)/~
但是有个小问题，我们有可能在角块加的时候，使原本有序的一块变得乱序，及时不是乱序的，块里边的数也改变了，于是我们还得加一个步骤，就是整块重构。
重构其实也很简单，就是直接将这个块清空，然后把修改过后的数放进原这块的vector，然后排个序，就完事了。
最后分析一下复杂度 ：
| 预处理 | nlogS |
| 区间加 | S(SlogS) |
| 区间小于k的个数 | SlogS |
所以总体的复杂度是 O（nlogS+mSlogS）
S取 sqrtn 或 n/m
上代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e4+5; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } inline void print(int x) { if(x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); } int size;int belong[maxn],a[maxn],taga[maxn]; vector<int>s[505]; int n; inline void reconstruct(int pos) { s[pos].clear(); for(int i=(pos-1)*size+1;i<=min(size*pos,n);i++)s[pos].push_back(a[i]); sort(s[pos].begin(),s[pos].end()); } inline void add(int l,int r,int k) { for(int i=l;i<=min(belong[l]*size,r);i++)a[i]+=k; reconstruct(belong[l]); if(belong[l]!=belong[r]) { for(int i=(belong[r]-1)*size+1;i<=r;i++)a[i]+=k; reconstruct(belong[r]); } for(int i=belong[l]+1;i<=belong[r]-1;i++)taga[i]+=k; } inline int search(int l,int r,int k) { int ans=0; for(int i=l;i<=min(belong[l]*size,r);i++)if(a[i]+taga[belong[i]]<k)ans++; if(belong[l]!=belong[r]) { for(int i=(belong[r]-1)*size+1;i<=r;i++)if(a[i]+taga[belong[i]]<k)ans++; } for(int i=belong[l]+1;i<=belong[r]-1;i++) { int x=k-taga[i]; ans+=lower_bound(s[i].begin(),s[i].end(),x)-s[i].begin(); } return ans; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); size=sqrt(n); for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1,s[belong[i]].push_back(a[i]); for(int i=1;i<=belong[n];i++)sort(s[i].begin(),s[i].end()); for(int i=1;i<=n;i++) { int cz,l,r,k; cz=read();l=read();r=read();k=read(); if(cz==0)add(l,r,k); if(cz==1)print(search(l,r,k*k)),putchar('\n'); } return 0; }
给出题目链接——loj分块入门2
2.区间加，区间第k小
看到第 k 小,我们首先想到的是动态开点线段树——主席树，但是看到区间加，主席树就熄火了，平衡树似乎也很难做到，于是我们考虑万能的分块。
这一题与上一题类似，我们可以把这些操作也放在vector里边。我们将每块对应的数放进一个vector并将每一块排序，区间加直接整块打tag，角块每个数暴力加并重新排序。区间第k小，我们考虑二分套二分：第 k 小就在这个序列中比这个数小的个数有 k 个，
于是我们在外围二分一个数值，内部用上一题的方法统计比传进来的这个数值小的个数，最后直接输出就OK了，具体看代码。
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks") #pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx") #include<bits/stdc++.h> #define size block typedef long long ll; using namespace std; const int maxn=1e5+5; const ll Inf=9999999999; struct istream{ char buf[23333333],*s; inline istream(){ buf[fread(s=buf,1,23333330,stdin)]='\n'; fclose(stdin); } inline istream&operator>>(int&d){ d=0; for(;!isdigit(*s);++s); while(isdigit(*s)) d=(d<<3)+(d<<1)+(*s++^'0'); return*this; } }read; /*inline void print(int x) { if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; for(register int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; }*/ struct ostream{ char buf[8000005],*s; inline ostream(){s=buf;} inline ostream&operator<<(int d){ if(!d){ *s++='0'; }else{ static int w; for(w=1;w<=d;w*=10); for(;w/=10;d%=w)*s++=d/w^'0'; } return*this; } inline ostream&operator<<(const char&c){*s++=c;return*this;} inline void flush(){ fwrite(buf,1,s-buf,stdout); s=buf; } inline~ostream(){flush();} }print; int a[maxn],belong[maxn],tag[maxn]; vector<int>s[505]; int block;int n,m; inline void reduce(int pos) { s[pos].clear(); for(register int i=(pos-1)*size+1;i<=min(pos*size,n);i++)s[pos].push_back(a[i]); sort(s[pos].begin(),s[pos].end()); } inline void add(int l,int r,int k) { for(register int i=l;i<=min(belong[l]*size,r);i++)a[i]+=k; reduce(belong[l]); if(belong[l]!=belong[r]) { for(register int i=(belong[r]-1)*size+1;i<=r;i++)a[i]+=k; reduce(belong[r]); } for(register int i=belong[l]+1;i<=belong[r]-1;i++)tag[i]+=k; } inline bool _find(int l,int r,int sum,int emm) { int ans=0; for(register int i=l;i<=min(belong[l]*size,r);i++)if(a[i]+tag[belong[l]]<sum)ans++; if(belong[l]!=belong[r]) { for(register int i=(belong[r]-1)*size+1;i<=r;i++)if(a[i]+tag[belong[r]]<sum)ans++; } for(register int i=belong[l]+1;i<=belong[r]-1;i++) { int x=sum-tag[i]; ans+=lower_bound(s[i].begin(),s[i].end(),x)-s[i].begin(); } return ans<emm?true:false; } inline ll get(int l,int r,bool x) { ll m=x?Inf:-Inf; for(register int i=l;i<=min(belong[l]*size,r);i++)m=x?min(m,(ll)a[i]+tag[belong[l]]):max(m,(ll)a[i]+tag[belong[l]]); if(belong[l]!=belong[r]) { for(register int i=(belong[r]-1)*size+1;i<=r;i++)m=x?min(m,(ll)a[i]+tag[belong[r]]):max(m,(ll)a[i]+tag[belong[r]]); } for(register int i=belong[l]+1;i<=belong[r]-1;i++) { m=x?min(m,(ll)s[i][0]+tag[i]):max(m,(ll)s[i][size-1]+tag[i]); } return m; } inline ll search(int l,int r,int k) { ll m=get(l,r,1),n=get(l,r,0); while(m<n) { ll mid=((m+n)>>1)+1ll; if(_find(l,r,mid,k))m=mid; else n=mid-1; } return m; } int main() { read>>n>>m;block=(int)1.0*sqrt(n)*log(n); for(register int i=1;i<=n;i++)read>>a[i]; for(register int i=1;i<=n;i++)belong[i]=(i-1)/size+1,s[belong[i]].push_back(a[i]); for(register int i=1;i<=belong[n];i++)sort(s[i].begin(),s[i].end()); for(register int i=1;i<=m;i++) { int cz,l,r,k; read>>cz>>l>>r>>k; if(cz==1){int p=search(l,r,k);print<<p<<'\n';} else add(l,r,k); } }
但是这样很暴力，复杂度大概是 O(n√nlog2n)的,所以我们考虑优化。
首先上一句名言：一杯茶，一包烟，一个块长调一天。
祝你们调块长顺利昂(
块长大概想我上面那样，取 sqrt(n) 大一点点是最优的。
第二就是，重排的时候，可以用归并排序，时间大概是线性的。
第三，两个边零散点二分的时候，用归并排序讲和成一个块，这样就可以用log^2的时间复杂度求出，或者记录询问的 l,r 区间，之后通过二分来确定询问范围之类的，具体看代码：
#pragma GCC optimize("O3") #pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks") #pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx") #include<bits/stdc++.h> using namespace std; class istream{ char buf[20000003],*s; public: inline istream(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif fread(s=buf,1,20000003,stdin); fclose(stdin); } inline istream&operator>>(int&rhs){ int f=rhs=0; for(;!isdigit(*s);++s)f=*s=='-'; for(;isdigit(*s);) rhs=(rhs<<3)+(rhs<<1)+(*s++^'0'); if(f)rhs=-rhs; return*this; } }read; class ostream{ char buf[5000005],*s; public: inline ostream(){s=buf;} inline ostream&operator<<(int rhs){ if(rhs<0)*s++='-',rhs=-rhs; if(rhs==0){ *s++='0'; return*this; } static int w; for(w=1;w<=rhs;w*=10); for(w/=10;w;w/=10)*s++=(rhs/w)^'0',rhs%=w; return*this; } inline ostream&operator<<(const char&rhs){*s++=rhs;return*this;} inline~ostream(){ fwrite(buf,1,s-buf,stdout); } }print; const int maxn=1e5+5; int n,m; struct node { int d,pos; }p[maxn],fz[maxn],fz2[maxn]; int size; inline bool cmp(node a,node b){return a.d<b.d;} int a[maxn]; int askl[maxn],askr[maxn],ask[maxn]; int tl,tr,tmi; int belong[maxn],L[maxn],R[maxn],atag[maxn]; int main() { read>>n>>m;size=sqrt(n)*5; for(int i=1;i<=n;i++)read>>a[i]; for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1; for(int i=1;i<=belong[n];i++)L[i]=R[i-1]+1,R[i]=i*size; R[belong[n]]=n; for(int i=1;i<=belong[n];i++) { for(int j=L[i];j<=R[i];j++) { p[j].d=a[j];p[j].pos=j; } sort(p+L[i],p+R[i]+1,cmp); } for(int cnt=1;cnt<=m;cnt++) { int opts,l,r,k;read>>opts>>l>>r>>k; int ql=belong[l],qr=belong[r]; if(opts==2) { if(ql==qr) { for(int i=l;i<=r;i++)a[i]+=k; tl=tr=0,tmi=R[ql]; for(int i=L[ql];i<=R[ql];i++) { if(l<=p[i].pos&&p[i].pos<=r)p[i].d+=k,fz[++tl]=p[i]; else fz2[++tr]=p[i]; } while(tl&&tr) { if(fz[tl].d>=fz2[tr].d)p[tmi--]=fz[tl--]; else p[tmi--]=fz2[tr--]; } while(tl)p[tmi--]=fz[tl--]; while(tr)p[tmi--]=fz2[tr--]; } else { for(int i=l;i<=R[ql];i++)a[i]+=k; tl=tr=0,tmi=R[ql]; for(int i=L[ql];i<=R[ql];i++) { if(l<=p[i].pos&&p[i].pos<=R[ql])p[i].d+=k,fz[++tl]=p[i]; else fz2[++tr]=p[i]; } while(tl&&tr) { if(fz[tl].d>=fz2[tr].d)p[tmi--]=fz[tl--]; else p[tmi--]=fz2[tr--]; } while(tl)p[tmi--]=fz[tl--]; while(tr)p[tmi--]=fz2[tr--]; for(int i=L[qr];i<=r;i++)a[i]+=k; tl=tr=0,tmi=R[qr]; for(int i=L[qr];i<=R[qr];i++) { if(L[qr]<=p[i].pos&&p[i].pos<=r)p[i].d+=k,fz[++tl]=p[i]; else fz2[++tr]=p[i]; } while(tl&&tr) { if(fz[tl].d>=fz2[tr].d)p[tmi--]=fz[tl--]; else p[tmi--]=fz2[tr--]; } while(tl)p[tmi--]=fz[tl--]; while(tr)p[tmi--]=fz2[tr--]; for(int i=belong[l]+1;i<=belong[r]-1;i++)atag[i]+=k; } } else if(opts==1) { int ans=0; if(k>r-l+1){puts("-1");continue;} int Lm=-2000000000,Rm=2000000000; for(int i=ql;i<=qr;i++){ Lm=min(p[L[i]].d+atag[i],Lm); Rm=max(p[R[i]].d+atag[i],Rm); askl[i]=L[i],askr[i]=R[i],ask[i]=L[i]-1; } while(Lm<=Rm) { int mid=(Lm+Rm)>>1;int sum=0; for(int i=l;i<=min(r,R[ql]);i++)if(a[i]+atag[ql]<=mid)sum++; if(ql!=qr) { for(int i=L[qr];i<=r;i++)if(a[i]+atag[qr]<=mid)sum++; } for(int i=ql+1;i<=qr-1;i++) { int ffl=askl[i],ffr=askr[i],mmd;ask[i]=L[i]-1; while(ffl<=ffr) { mmd=(ffl+ffr)>>1; if(p[mmd].d+atag[i]<=mid){ffl=mmd+1;ask[i]=mmd;} else ffr=mmd-1; } sum+=ask[i]-L[i]+1; } if(sum>=k) { ans=mid; Rm=mid-1; for(int i=ql+1;i<=qr-1;i++)askr[i]=ask[i]; } else { Lm=mid+1; for(int i=ql+1;i<=qr-1;i++)askl[i]=max(ask[i],L[i]); } } print<<ans<<'\n'; } } }
给出题目链接——
P5356 [Ynoi2017]由乃打扑克
原文链接: https://www.cnblogs.com/bovine-kebi/p/13192862.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367226
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
