点击查看目录
众所周知，线段树是把一个区间分为两个区间维护，再不断往下分，直到分到单个点。
虽然它效率高，但很难处理一些特殊问题（如求区间众数）。
那有没有更方便操作而又高效的数据结构呢？
有！分块！
分块是直接把长为 (n) 的序列划分成 (\sqrt{n}) 份，每份长为 (\sqrt{n})。
更新或修改时，先对整块进行整体处理，再对构不成整块的点单独处理。
这样的话，分块的预处理时间复杂度为 (\Theta(n))，查询/修改复杂度为 (\Theta(n\sqrt{n}))。
既然是树状数组模板题，那肯定不能用树状数组做！
点击查看代码
const int N=5e5+10,SN=1000,inf=1<
一种离线算法，可以用 ((n+q)\sqrt{n}) 的时间解决所有询问。
首先对所有查询的左端点 (l) 进行分块（把左端点在区间 ([k\sqrt{n}+1,(k+1)\sqrt{n}]) 的分成一块），然后进行排序：对于块相同的，对右端点排序；块不同的，对左端点排序。
排序完之后就可以解决查询了。第一个查询我们直接暴力解决，之后的每个查询我们都通过移动上一个询问的左右端点来解决。
这不是 $n^2$ 的吗？为啥是复杂度是对的？
这就是排序的作用了。
排序之后相邻询问的左端点变化在 (\sqrt{n}) 内，全部跑完复杂度 (\Theta(q\sqrt{n}))。
然后相同块内右端点是递增的，所以最坏也只需要算 (n) 次，全部跑完复杂度 (\Theta(n\sqrt{n}))。
综上所述，时间复杂度为 (\Theta((n+q)\sqrt{n}))。
一个优化：奇偶性排序
仔细想想可以发现，每个块内的询问处理完了跳到下一个块时，总是会先用 (\Theta(n+)) 的时间跑回最左边再开始往右跑。
但实际上在往左跑时我们就可以处理掉询问。
所以我们在排序时判断一下块的奇偶性，奇块内部对右端点升序排序，偶块内部对右端点降序排序。
答案显然是：
[\frac{\sum_{i=1}^{n}(C_{cnt_i}^2-C_{cnt_i-1}^2)}{C_{r-l+1}^2} ]
其中 (cnt_i) 表示颜色 (i) 在区间中出现的次数。
化简一下分子：
[\begin{aligned} &\sum_{i=1}^{n}(C_{cnt_i}^2-C_{cnt_i-1}^2)\ =&\sum_{i=1}^{n}(\frac{cnt_i(cnt_i-1)}{2}-\frac{(cnt_i-1)(cnt_i-2)}{2})\ =&\sum_{i=1}^{n}\frac{(cnt_i-1)(cnt_i-(cnt_i-2))}{2}\ =&\sum_{i=1}^{n}\frac{2(cnt_i-1)}{2}\ =&\sum_{i=1}^{n}cnt_i-1\ \end{aligned} ]
然后直接用莫队算，每次弹出/加入一个数时更新 (cnt_i)，顺便更新一下总和。
点击查看代码
const ll N=5e4+10,P=998244353;
ll n,m,sn,c[N],ans[N][2];
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
class MODUI{
public:
ll cnt[N],sum;
class Q{
public:
ll l,r,id,k;
inline void Join(ll le,ll rr,ll iid){
l=le,r=rr,id=iid;
k=(le-1)/sn+1;
return;
}
bool operatorp.r;
}
}q[N];
inline void Join(ll le,ll rr,ll iid){q[iid].Join(le,rr,iid);}
inline void Add(ll i){sum+=cnt[c[i]]++;}
inline void Del(ll i){sum-=--cnt[c[i]];}
inline void Solve(){
sort(q+1,q+m+1);
ll l=1,r=0;
_for(i,1,m){
if(q[i].l==q[i].r){
ans[q[i].id][0]=0;
ans[q[i].id][1]=1;
continue;
}
while(l>q[i].l)Add(--l);
while(rq[i].r)Del(r--);
ans[q[i].id][0]=sum;
ans[q[i].id][1]=(r-l+1)*(r-l)/2;
}
}
}md;
namespace SOLVE{
inline ll rnt() {
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=x*10+(c^48),c=getchar();
return x*w;
}
inline void In(){
n=rnt(),m=rnt();
sn=sqrt(n);
_for(i,1,n)c[i]=rnt();
_for(i,1,m){
ll l=rnt(),r=rnt();
md.Join(l,r,i);
}
md.Solve();
_for(i,1,m){
if(!ans[i][0])puts("0/1");
else{
ll g=gcd(ans[i][0],ans[i][1]);
ans[i][0]/=g,ans[i][1]/=g;
printf("%lld/%lld\n",ans[i][0],ans[i][1]);
}
}
}
}
普通莫队是不能进行修改的，我们怎样才能让它支持修改呢？
在普通莫队中的查询区间 ([l,r]) 我们可以看成二位坐标系上的点，那么在带修莫队中我们再加上一维：时间，即这次查询是在几次修改之后，我们可以用类似 (\Theta(1)) 移动左右端点的方法移动时间这一维。
简单来说，我们存一下每个修改的修改位置上修改前和修改后的值。解决查询时如果当前修改次数少了就暴力加入少了的修改，多了就暴力还原回去。
设块长为 (s)，则每次左右端点最多移动 (s) 次，总复杂度 (\Theta(n\cdot s))。
块数为 (q=\tfrac{n}{s})，每次左右端点所在块改变时，时间移动 (n) 次，否则时间单调递增，总共移动 (n) 次。左端点有 (q) 种，右端点有 (q) 种，总复杂度 (\Theta(n\cdot q^2))。
则最优 (s=n^{\tfrac{2}{3}})，总复杂度 (\Theta(n^{\tfrac{5}{3}}))。
就是个板子，没什么说的（
注意一些细节就可以了。
点击查看代码
const ll N=2e5+10,P=998244353,inf=1<q[i].x)AddP(a[--l]);
while(rq[i].y)DelP(a[r--]);
while(xuq[i].lx)DelX(xu--,q[i].x,q[i].y);
ans[q[i].id]=num;
}
return;
}
}md;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<'Z')c=getchar();
return c;
}
inline void wnt(ll x,char c){
static int st[35];int top=0;
do{st[top++]=x%10;x/=10;}while(x);
while(top)putchar(st[--top]+'0');
putchar(c);
return;
}
inline void In(){
n=rnt(),m=rnt(),sn=pow(n,2.0/3.0);
_for(i,1,n)b[i]=a[i]=rnt();
_for(i,1,m){
char op=rch();ll x=rnt(),y=rnt();
md.Join(op,x,y,i);
if(op=='R')ans[i]=-1;
}
md.Solve();
_for(i,1,m)if(ans[i]!=-1)wnt(ans[i],'\n');
return;
}
}
练习题
暴力的思路就是直接存弹几步弹飞，显然会被卡 T。
考虑如何优化。
我们不存弹几步弹飞，而是 弹几步会弹出这个块。
更新时，更新的值只与本块内的蹦床弹几步会弹出这个块有关系，所以直接暴力重构该块即可，时间复杂度为 (\Theta(\sqrt{n}))。
查询时，实际上最多只会弹 (\sqrt{n}) 次，所以时间复杂度为 (\Theta(\sqrt{n}))。
点击查看代码
const int N=2e5+10,SN=1000,inf=1<
区间众数问题。
此时如果维护每个块内每个数的数量，直接合并会 TLE。
那么我们就预处理出块 (i) 到块 (j) 每个数的数量和众数 (bl_{i,j})，众数只可能是 整块本身的众数 或是 有散块后才变成众数的数，那么我们把所有散块放到整块里并更新众数即可。
这样不会 TLE 了，但会 MLE。
那如何不用占空间的的存储方式来快速求出每个数的数量？
开一个 vector 存每个数出现的位置，来辅助找出每个数在每个块第一次/最后一次出现是在整个数列中第几次出现，两者之差加一就是这个块中这个数的数量（需要二分）。
这样我们只需储存 (bl_{i,j})，对于散块，我们找到每个数在区间中第一次/最后一次出现是在整个数列中第几次出现，两者做差再加一即为它们的数量（此时不用二分）。
预处理 (\Theta(n^2))（准确说应该是：设 (s=块数)，时间复杂度为 (\Theta(s^2n))，因此可以通过调整块长来降低复杂度，卡过此题），单次查询 (\Theta(\sqrt{n}))。
点击查看代码
const int N=4e4+10,SN=250,inf=1<wz[N];
namespace LISAN{
ll ls[N];
inline void LiSan(){
_for(i,1,n)ls[i]=a[i];
sort(ls+1,ls+n+1);
len=unique(ls+1,ls+n+1)-ls-1;
_for(i,1,n){
b[i]=lowb(ls,len,a[i]);
c[b[i]]=a[i];
}
return;
}
}
class Block{
public:
ll sn,ka[N],wl[SN][N],wr[SN][N];
class BL{
public:
ll l,r;
ll mx,mw;
}bl[SN][SN];
#define l(ii,jj) bl[ii][jj].l
#define r(ii,jj) bl[ii][jj].r
#define mx(ii,jj) bl[ii][jj].mx
#define mw(ii,jj) bl[ii][jj].mw
inline void Init(){
sn=sqrt(n);
ka[n+1]=sn+1;
_for(i,1,sn){
l(i,i)=r(i-1,i-1)+1;
r(i,i)=(i==sn)?n:l(i,i)+sn-1;
_for(j,1,n){
wl[i][j]=lower_bound(wz[j].begin(),wz[j].end(),l(i,i))-wz[j].begin();
wr[i][j]=lower_bound(wz[j].begin(),wz[j].end(),r(i,i)+1)-wz[j].begin();
}
_for(j,l(i,i),r(i,i)){
ka[j]=i,la[j]=-1;
ll cnt=wr[i][b[j]]-wl[i][b[j]];
if(cnt>mx(i,i)||(cnt==mx(i,i)&&b[j]mx(i,j)||(cnt==mx(i,j)&&kqwq.mx||(cnt==qwq.mx&&b[i]qwq.mx||(cnt==qwq.mx&&b[i]mx||(cnt==mx&&b[i]
《关于我忘了调用初始化函数于是交了二十多遍这件事》
为了方便计数，我们新开一个数组，用来存对每个块内部进行排序后的结果，复杂度 (\Theta(\sqrt{n}\sqrt{n}\log_2\sqrt{n})=O(n\log_2{\sqrt{n}}))。
每次更改，对于整块直接打 (tag)，对于散块直接更改原数组并重新排一遍序，复杂度 (\Theta(\sqrt{n}\log_2{\sqrt{n}}))。
每次查询，散块直接暴力算答案，整块用 lower_bound() 去算，注意要将查询值 (c) 减去该块 (tag) 以达到区间加的效果，复杂度依旧是 (\Theta(\sqrt{n}\log_2{\sqrt{n}}))。
点击查看代码
const int N=1e6+1,SN=1001;
int n,q,a[N],ans;
class Block{
public:
int sn,b[N],ka[N];
class BL{
public:
int l,r;
int tag;
}bl[SN];
inline void ReSort(int kuai){
_for(i,bl[kuai].l,bl[kuai].r)b[i]=a[i];
sort(b+bl[kuai].l,b+bl[kuai].r+1);
}
inline void Init(){
sn=sqrt(n);
_for(i,1,sn){
bl[i].l=bl[i-1].r+1;
bl[i].r=(i==sn)?n:bl[i].l+sn-1;
_for(j,bl[i].l,bl[i].r)ka[j]=i;
ReSort(i);
}
return;
}
inline void Update(int l,int r,int val){
int k1=ka[l],k2=ka[r];
if(k1==k2){
_for(i,l,r)a[i]+=val;
ReSort(k1);
}
else{
_for(i,l,bl[k1].r)a[i]+=val;
ReSort(k1);
_for(i,bl[k2].l,r)a[i]+=val;
ReSort(k1);
_for(i,k1+1,k2-1)bl[i].tag+=val;
}
return;
}
inline int Query(int l,int r,int val){
int k1=ka[l],k2=ka[r],ans=0;
if(k1==k2)
_for(i,l,r)ans+=(a[i]>=val-bl[k1].tag);
else{
_for(i,l,bl[k1].r)ans+=(a[i]>=val-bl[k1].tag);
_for(i,bl[k2].l,r)ans+=(a[i]>=val-bl[k2].tag);
_for(i,k1+1,k2-1){
int w=lower_bound(b+bl[i].l,b+bl[i].r+1,val-bl[i].tag)-b;
ans+=bl[i].r-w+1;
}
}
return ans;
}
}bl;
用类似于蒲公英那道题的方法，存储第 (l\sim r) 块每种颜色的数量和每种颜色的数量的平方的前缀和，散块直接加到整块里算贡献即可。
算贡献的方法：当一种颜色的数量 (cnt_i) 加一后，就会对答案增加 (2cnt_i-1) 的贡献。
设块数为 (sn)，则预处理复杂度为 (\Theta(sn^2m))，全部查询复杂度为 (\Theta(q\cdot\frac{n}{sn}))，则最优 (sn=n^{\tfrac{1}{3}})，设为 (50) 即可。
空间复杂度是 (\Theta(sn^2m))。所以说上边的你都不用算你直接像我一样看能不能开下就行了。
（感觉存储第 (l\sim r) 块的东西算是分块题的一种经典套路了吧。）
点击查看代码
const ll N=5e4+10,M=2e4+10,SN=60,P=998244353;
ll n,m,q,c[N],cnt[M],f[M],ans;
class BLOCK{
public:
ll sz,sn=50,ka[N],num[SN][SN][M],an[SN][SN][M];
class BL{public:ll l,r;}bl[SN];
inline void Pre(){
sz=n/sn;
_for(i,1,sn){
bl[i].l=bl[i-1].r+1;
bl[i].r=(i==sn)?n:bl[i].l+sz-1;
_for(j,bl[i].l,bl[i].r){
ka[j]=i;
++num[i][i][c[j]];
}
_for(j,1,m)an[i][i][j]=an[i][i][j-1]+num[i][i][j]*num[i][i][j];
}
_for(i,1,sn)_for(j,i+1,sn)_for(k,1,m){
num[i][j][k]=num[i][j-1][k]+num[j][j][k];
an[i][j][k]=an[i][j][k-1]+num[i][j][k]*num[i][j][k];
}
return;
}
inline ll Query(ll l,ll r,ll a,ll b){
ll k1=ka[l],k2=ka[r],ans=0;
if(k1==k2){
_for(i,l,r)cnt[c[i]]=0;
_for(i,l,r){
if(c[i]b)continue;
ans+=(cnt[c[i]]<b)continue;
if(!cnt[c[i]])cnt[c[i]]=num[k1+1][k2-1][c[i]];
ans+=(cnt[c[i]]<b)continue;
if(!cnt[c[i]])cnt[c[i]]=num[k1+1][k2-1][c[i]];
ans+=(cnt[c[i]]<
直接套莫队板子即可。
点击查看代码
const ll N=5e4+10,P=998244353;
ll n,m,k,sn,a[N],ans[N];
class MODIU{
public:
ll sum,c[N];
class Q{
public:
ll l,r,id,k;
inline void Join(ll le,ll ri,ll i){l=le,r=ri,id=i,k=(le-1)/sn+1;return;}
inline bool operatorp.r;
}
}q[N];
inline void Join(ll le,ll ri,ll i){q[i].Join(le,ri,i);return;}
inline void Add(ll i){sum-=c[i]*c[i],++c[i],sum+=c[i]*c[i];}
inline void Del(ll i){sum-=c[i]*c[i],--c[i],sum+=c[i]*c[i];}
inline void Solve(){
sort(q+1,q+m+1);
ll l=1,r=0;
_for(i,1,m){
while(l>q[i].l)Add(a[--l]);
while(rq[i].r)Del(a[r--]);
ans[q[i].id]=sum;
}
}
}md;
namespace SOLVE{
inline ll rnt() {
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=x*10+(c^48),c=getchar();
return x*w;
}
inline void wnt(ll x){
static int st[35];int top=0;
do{st[top++]=x%10;x/=10;}while(x);
while(top)putchar(st[--top]+'0');
return;
}
inline void In(){
n=rnt(),m=rnt(),k=rnt();
sn=sqrt(n);
_for(i,1,n)a[i]=rnt();
_for(i,1,m){
ll l=rnt(),r=rnt();
md.Join(l,r,i);
}
md.Solve();
_for(i,1,m)wnt(ans[i]),putchar('\n');
}
}
用莫队离线下来处理，用树状数组维护数的数量和数的种类。
复杂度是 (\Theta(n\sqrt{m}\log_2{n}))，勉强能过。
点击查看代码
const ll N=1e5+10,P=998244353;
ll n,m,sn,c[N],ans[N][2];
class MODUI{
public:
ll jl[N];
class BIT{
public:
ll b[N];
inline void Update(ll x,ll y){while(x&&xp.r;
}
}q[N];
inline void Join(ll le,ll ri,ll aa,ll bb,ll i){q[i].Join(le,ri,aa,bb,i);}
inline void Add(ll i){
b1.Update(c[i],1);
if(!jl[c[i]])b2.Update(c[i],1);
++jl[c[i]];
}
inline void Del(ll i){
b1.Update(c[i],-1);
--jl[c[i]];
if(!jl[c[i]])b2.Update(c[i],-1);
}
inline void Solve(){
sort(q+1,q+m+1);
ll l=1,r=0;
_for(i,1,m){
while(l>q[i].l)Add(--l);
while(rq[i].r)Del(r--);
ans[q[i].id][0]=b1.Query(q[i].b)-b1.Query(q[i].a-1);
ans[q[i].id][1]=b2.Query(q[i].b)-b2.Query(q[i].a-1);
}
return;
}
}md;
namespace SOLVE{
inline ll rnt() {
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=x*10+(c^48),c=getchar();
return x*w;
}
inline void wnt(ll x){
static int st[35];int top=0;
do{st[top++]=x%10;x/=10;}while(x);
while(top)putchar(st[--top]+'0');
return;
}
inline void In(){
n=rnt(),m=rnt();
sn=sqrt(n);
_for(i,1,n)c[i]=rnt();
_for(i,1,m){
ll l=rnt(),r=rnt(),a=rnt(),b=rnt();
md.Join(l,r,a,b,i);
}
md.Solve();
_for(i,1,m)wnt(ans[i][0]),putchar(' '),wnt(ans[i][1]),putchar('\n');
return;
}
}
这道题直接用莫队，用分块维护值域上连续块最大值，想起来非常容易。
接下来开始分析上面每道题都在分析的重点内容：块长与时间复杂度。
在分析了半天之后，我分析出了理论最优块长：(n^{\tfrac{1}{3}})。
但是交上去之后 TLE 了。
于是，在与这道题痛苦地争斗许久后，我发现直接设块长为 (700) 是最优的，同时悟到了块长分析法的真谛：
什么理论最优复杂度！什么估出复杂度解方程！
造组极限数据跑，块长一百一百地加！
跑得最快的就是正确块长，别和我说什么理论，跑不过这个块长就是垃圾！
点击查看代码
const ll N=2e5+10,SN=1000;
ll n,m,sn,sz,a[N],ans[N];
class MODUI{
public:
class Q{
public:
ll i,l,r,k;
inline void Join(ll id,ll le,ll ri){i=id,l=le,r=ri,k=(l-1)/sz+1;}
inline bool operatorp.r;
}
}q[N];
class BLOCK{
public:
ll ka[N],b[N];
class BL{
public:
ll l,r,s;
ll q,z,h;
bool full;
}bl[SN];
inline void Init(){
_for(i,1,sn){
bl[i].l=bl[i-1].r+1;
bl[i].r=(i==sn)?n:bl[i].l+sz-1;
bl[i].s=bl[i].r-bl[i].l+1;
_for(j,bl[i].l,bl[i].r)ka[j]=i;
}
return;
}
inline void Add(ll i){
ll k=ka[i],cnt=0;
b[i]=!b[i],bl[k].full=0;
bl[k].q=bl[k].z=bl[k].h=0;
_for(j,bl[k].l,bl[k].r){
if(!b[j])break;
++bl[k].q;
}
for_(j,bl[k].r,bl[k].l){
if(!b[j])break;
++bl[k].h;
}
_for(j,bl[k].l,bl[k].r){
cnt=(cnt+1)*b[j];
bl[k].z=max(bl[k].z,cnt);
}
if(bl[k].q==bl[k].s)bl[k].full=1;
return;
}
inline ll Query(){
ll num=0,an=0;
_for(i,1,sn){
if(bl[i].full)num+=bl[i].s;
else{
num+=bl[i].q;
an=max(an,max(num,bl[i].z));
num=bl[i].h;
}
}
an=max(an,num);
return an;
}
}bl;
inline void Join(ll id,ll le,ll ri){q[id].Join(id,le,ri);}
inline void Solve(){
sort(q+1,q+m+1);
ll l=1,r=0;
bl.Init();
_for(i,1,m){
while(l>q[i].l)bl.Add(a[--l]);
while(rq[i].r)bl.Add(a[r--]);
ans[q[i].i]=bl.Query();
}
return;
}
}md;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<
[\Huge{\mathfrak{The\ End}} ]
Original: https://www.cnblogs.com/Keven-He/p/Block.html
Author: Keven-He
Title: 「学习笔记」分块与莫队
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587569/
转载文章受原作者版权保护。转载请注明原作者出处！