根号数据结构之分块总结
本文主要选讲一类根号数据结构分块和有关的问题
本文大概会涉及到的知识 普通分块，根号分治，根号重构
我们会先根据前三块来类比一一介绍一下
首先最常见的根号数据结构就是分块
首先普通的分块就是我们考虑在处理有序表的时候通常有时候会遇到难处理的问题，我们用比较大众的数据结构像是线段树，树状数组解决不了的时候，我们通常会考虑用分块，举个例子像是我们平时通常常见的维护最大值最小值我们可以用线段树树状数组ST表这种数据结构开快速合并处理，但是假设我们要维护一下奇怪的函数值，或者是诸如每个点维护一个单调队列这种我们就不是能很方便有其他数据结构，这个时候我们通常会考虑分块等根号数据结构
分块的思想其实就是暴力，我们容易用一种分块把相邻或者有相似性质的元素放在一起，如果需要处理我们就会一起处理，来减少复杂度的开销，但是我们还是基于暴力的思想来写代码，通常是利用整块和零散部分分治的思想来做
在大部分的时候我们分块通常要平衡一下块长，使得复杂度最优，大部分情况去块长K=sqrt(n)
我们用几个简单的例子来引入普通的序列分块：
这里只是对于几个经典的数据结构问题说一下做法，并不会给出代码
1 单点查询 区间求和
我们单点查询显然可以做到O(1)的复杂度，但是暴力解决问题的瓶颈在于O(n)的区间求和
那么我们考虑假设我们按照普通的序列分块
然后我们考虑区间求和就可以做到O(N/K+K)的复杂度
那么我们在K去sqrt(n)的时候就可以接受
于是我们只需要记录每块的和然后我们查询的时候只需要查到be[l]~be[r]的区间就可以了
对于一块已经能快速处理的我们可以直接O(1)求和
现在给出我们序列分块的简单代码
K=sqrt(n); for(int i=1;i<=n;i++) be[i]=(i-1)/K+1;
只是借助本题大概理解下分块的思想，下面进入正题
2 无修改查询区间逆序对的个数
我们最初预处理出G[l][r]代表be[l]~be[r]的逆序对个数
然后暴力用边角处理一下，只需要对于块的前缀维护一个有序表即可
3 区间加以及 Q个询问，求区间<=x的数的个数
我们考虑还是按照序列分块
我们每次区间加的时候我们对于整块直接区间加维护一个tag，零散部分只会涉及到2个块，我们每次修改的时候都重构一次
这里的重构通常是我们维护一个有序表，方便快速查询一个块内某个值域范围内的数的个数
然后我们区间查询的时候我们只需要考虑整块的我们利用已知的tag和二分块内<=一个数的个数，然后对于零散部分暴力做就可以了，这样是一个O(nsqrt(n)log(n))的（这里我们钦定n,Q同阶）
然后有了这个的前置知识，我们来看一道分块辅助做的问题
洛谷P3863 序列
https://www.luogu.com.cn/problem/P6349
给定一个长度为n的序列，给出q个操作，形如：
1 表示将序列下标介于[l,r]的元素加上x（请注意，x可能为负）
2 p y 表示查询A[p]在过去的多少秒时间内不小于y
开始时为第0秒，第i个操作发生在第i秒。
我们遇到这样的问题直接处理不是非常方便，我们考虑换一个方向来处理一下
我们把时间轴旋转一下，就变成了我们对于每个操作，其实就是差分一下，在l处打上+x的标记，在r+1处打上-x的标记
那么我们按着元素的下标做，就变成了我们只需要支持一个区间加，然后查询一段时间以内在某个值域里面数的个数
我们直接离线下来，然后分块类似这刚刚讲的第三个问题做即可。
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pii pair<LL,LL>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline LL read(){
LL nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 100020
#define INF 1000000000
LL n,m,tim,ans[M]; LL a[M];
LL K,blg[M],L[M],R[M]; LL tg[M];
vector<LL>sta[420];
struct data{LL x,y,id;};
vector<pii >cod[M]; vector<data >vec[M];
inline void ins(LL x,LL y,LL z){cod[x].pb(mpt(z,y));}
inline void mdf_(LL l,LL r,LL x){for(LL i=l;i<=r;i++) a[i]+=(LL)x;}
inline LL qry_(LL l,LL r,LL x){LL ret=0; for(LL i=l;i<=r;i++) if(a[i]+tg[blg[i]]>=x)ret++; return ret;}
inline void rbd(LL x){
sta[x].clear(); for(LL i=L[x];i<=R[x];i++) sta[x].pb(a[i]);
sort(sta[x].begin(),sta[x].end());
}
inline LL get(LL pos,LL vl){return sta[pos].size()-(lower_bound(sta[pos].begin(),sta[pos].end(),vl)-sta[pos].begin());}
inline void mdf(LL l,LL r,LL x){
LL tl=blg[l],tr=blg[r];
if(tl+1>=tr){mdf_(l,r,x);rbd(tl),rbd(tr); return;}
mdf_(l,R[tl],x),mdf_(L[tr],r,x),rbd(tl),rbd(tr);
for(LL i=tl+1;i<tr;i++) tg[i]+=(LL)x;
}
inline LL qry(LL l,LL r,LL x){
LL tl=blg[l],tr=blg[r],ret=0;
if(tl+1>=tr) return qry_(l,r,x);
ret=qry_(l,R[tl],x)+qry_(L[tr],r,x);
for(LL i=tl+1;i<tr;i++) ret+=get(i,x-tg[i]);
return ret;
}
int main(){
n=read(),m=read();
for(LL i=1;i<=n;i++){LL x=read(); ins(i,0,x),ins(i+1,0,-x);}
for(LL i=1,op,x,y,z;i<=m;i++){
op=read(),x=read(),y=read();
if(op==1) z=read(),ins(x,i,z),ins(y+1,i,-z);
else vec[x].pb((data){i,y,++tim});
}
K=sqrt(m);
for(LL i=1;i<=m;i++) blg[i]=(i-1)/K+1;
blg[1]=blg[0];
for(LL i=1;i<=blg[m];i++) L[i]=INF,R[i]=-INF;
for(LL i=0;i<=m;i++) L[blg[i]]=min(L[blg[i]],i),R[blg[i]]=max(R[blg[i]],i);
for(LL i=1;i<=blg[m];i++) rbd(i);
for(LL i=1;i<=n;i++){
for(LL j=0,TP=cod[i].size();j<TP;j++) mdf(cod[i][j].sc,m,cod[i][j].fr);
for(LL j=0,TP=vec[i].size();j<TP;j++) ans[vec[i][j].id]=qry(0,vec[i][j].x-1,vec[i][j].y);
}
for(LL i=1;i<=tim;i++) printf("%lld\n",ans[i]);
return 0;
}
洛谷P3203 [HNOI2010]弹飞绵羊
每头羊有一个弹射的距离，每次会修改一头羊，或者询问一头羊会被弹多少次以后弹飞
我们考虑分块维护，但是这道题不能普通的序列分块维护
我们考虑还是按照根号K分块，然后我们暴力处理块内的跳步数，然后我们对于每次查询对于所有块直接求出答案就可以了
这是一种另外的思路，我们可以把修改和询问平衡一下，这个思路也可以理解成根号平衡，但是就在分块里讲了，然后根号是一个不错的选择，我们有时候可以直接把所有块都遍历一遍。
这道题的代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pii pair<int,int>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 200020
int n,K,to[M],blg[M],cnt[M],last[M],L[M],R[M],nowl,nowr;
inline int qry(int x){int ret=0; while(x<=n) ret+=cnt[x],x=last[x]; return ret;}
inline void rbd(int x){
int l=L[x],r=R[x];
for(int i=l;i<=r;i++) last[i]=-1;
for(int i=r;i>=l;i--) if(to[i]>r) last[i]=to[i],cnt[i]=1; else last[i]=last[to[i]],cnt[i]=cnt[to[i]]+1;
}
int main(){
n=read(),K=sqrt(n),memset(last,-1,sizeof(last));
for(int i=1;i<=n;i++) to[i]=read()+i,blg[i]=(i-1)/K+1;
for(int i=1;i<=blg[n];i++) L[i]=(i-1)*K+1,R[i]=min(i*K,n),rbd(i);
int m=read();
while(m--){
int opt=read(),x=read()+1;
if(opt==1) printf("%d\n",qry(x));
else to[x]=read()+x,rbd(blg[x]);
}
return 0;
}
P6325 [COCI2006-2007#4] ISPITI
https://www.luogu.com.cn/problem/P6325
求一个二维偏序的lower_bound
我们首先离散化下来，然后我们用分块来暴力二分，类似于二分的思路，但是这样的空间是线性的
相当于是那时间换空间，然后时间其实和两个log的树套树是类似的
分块二分的思路可以类似看一下代码
代码：
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pii pair<int,int>
#define pb push_back
#define mpt make_pair
#define fr first
#define sc second
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 200020
int n,num[M<<1],top,blg[M<<1],L[M<<1],R[M<<1];
int N,K,mx[M<<1],mxK[M<<1],tot,rev[M];
struct nd{int op,x,y;}q[M],sta[M];
set<pii >s[M<<1];
#define IT set<pii >::iterator
inline void ins(int x,int y,int id){s[x].insert(mpt(y,id)),mx[x]=max(mx[x],y),mxK[blg[x]]=max(mxK[blg[x]],y);}
inline int qry_(int x,int y){IT it=s[x].lower_bound(mpt(y,0)); return (*it).sc;}
inline void qry(int x,int y){
if(mx[x]>y){printf("%d\n",qry_(x,y+1));return;}
for(int i=x+1;i<=R[blg[x]];i++)
if(mx[i]>=y){printf("%d\n",qry_(i,y));return;}
for(int i=blg[x]+1;i<=N;i++)
if(mxK[i]>=y){
for(int j=L[i];j<=R[i];j++)
if(mx[j]>=y){printf("%d\n",qry_(j,y));return;}
}
puts("NE");
}
int main(){
n=read();
for(int i=1;i<=n;i++){
char ch[11]; scanf("%s",ch);
if(ch[0]=='D') q[i].op=1,q[i].x=read(),q[i].y=read(),num[++top]=q[i].x,num[++top]=q[i].y;
else q[i].op=2,q[i].x=read();
}
if(!top){
for(int i=1;i<=n;i++) if(q[i].op==2) puts("NE");
return 0;
}
sort(num+1,num+top+1),top=unique(num+1,num+top+1)-num-1,K=sqrt(top);
for(int i=1;i<=n;i++) if(q[i].op==1)
q[i].x=lower_bound(num+1,num+top+1,q[i].x)-num,q[i].y=lower_bound(num+1,num+top+1,q[i].y)-num,sta[rev[i]=++tot]=q[i];
for(int i=1;i<=top;i++) blg[i]=(i-1)/K+1;
N=blg[top];
for(int i=1;i<=N;i++) L[i]=(i-1)*K+1,R[i]=min(i*K,top);
for(int i=1;i<=n;i++)
if(q[i].op==1) ins(q[i].y,q[i].x,rev[i]);
else qry(sta[q[i].x].y,sta[q[i].x].x);
return 0;
}
BZOJ3787 GTY的文艺妹子序列
单点修改查区间逆序对
未完待续
查看20道真题和解析
