首先，我们知道，分块是一种优雅的暴力，他可以很灵活的变通，下面，我整理了几道分块的经典题目跟大家分享（持续更新中）：
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 |
| 区间小于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)的,所以我们考虑优化。
首先上一句名言：一杯茶，一包烟，一个块长调一天。
祝你们调块长顺利昂(
块长大概想我上面那样，取 logn*sqrt(n) 是最优的。
第二就是，重排的时候，可以用归并排序，时间大概是线性的。
第三，两个边零散点二分的时候，用归并排序讲和成一个块，这样就可以用log^2的时间复杂度求出。
代码等我码出来之后再给。
给出题目链接——
原文：https://www.cnblogs.com/bovine-kebi/p/13192862.html