分块与莫队算法

分块就是将数列分成很多块，对涉及的块做整体性的维护操作。类似与一个多分线段树。

代码比树状数组和线段树简单，效率比暴力高的，时间复杂度 O ( m n ) O(m \sqrt{n}) O(mn ​)。

  • 块的大小（块的长度），block=sqrt(n)
  • 块的数量，t
  • 块的左右边界，st[] 和 ed[]
  • 每个元素所属块，pos[i]=(i-1)/block+1

分块定义，初始化

int block=sqrt(n);
int t=n/block;
if(n%block) t++;
for(int i=1;i<=t;i++){
    st[i]=(i-1)*block+1;
    ed[i]=i*block;
}
ed[t]=n;
for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;

P2801 教主的魔法 - 洛谷

ll n,m,a[N],b[N],add[N];
ll t,st[N],ed[N],pos[N];
void change(int L,int R,ll d){//对[L,R]区间操作
	int p=pos[L],q=pos[R];//左右区间端点对应块
	if(p==q){//同一块，碎片
		for(int i=L;i<=R;i++) b[i]+=d;//暴力操作区间
		for(int i=st[p];i<=ed[p];i++) a[i]=b[i];//维护a数组
		sort(a+st[p],a+ed[p]+1);
	}else{
		for(int i=p+1;i<=q-1;i++) add[i]+=d;//整块操作
		for(int i=L;i<=ed[p];i++) b[i]+=d;//左碎片操作
		for(int i=st[p];i<=ed[p];i++) a[i]=b[i];
		sort(a+st[p],a+ed[p]+1);
		for(int i=st[q];i<=R;i++) b[i]+=d;//右碎片操作
		for(int i=st[q];i<=ed[q];i++) a[i]=b[i];
		sort(a+st[q],a+ed[q]+1);
	}
}
ll query(int L,int R,ll c){//在[L,R]中查询
	int p=pos[L],q=pos[R];//区间端点对应块
	ll ans=0;
	if(p==q){
		for(int i=L;i<=R;i++)//暴力操作碎片
			if(b[i]+add[p]>=c) ans++;
	}else{
		for(int i=p+1;i<=q-1;i++){//整块操作
			int x=lower_bound(a+st[i],a+ed[i]+1,c-add[i])-a;
			ans+=(ed[i]-x+1);
		}
		for(int i=L;i<=ed[p];i++)//左碎片暴力查询
			if(b[i]+add[p]>=c) ans++;
		for(int i=st[q];i<=R;i++)//右碎片暴力查询
			if(b[i]+add[q]>=c) ans++;
	}
	return ans;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];};//复制数组
	int block=sqrt(n);//块大小
	t=(n+block-1)/block;//块数量
	for(int i=1;i<=t;i++){
		st[i]=(i-1)*block+1;//块的左端点
		ed[i]=i*block;//块的右端点
	}
	ed[t]=n;//防止最后一块越界
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;//元素对应块
	for(int i=1;i<=n;i++) sort(a+st[i],a+ed[i]+1);//块内排序
	while(m--){
		char c;cin>>c;
		ll l,r,w;cin>>l>>r>>w;
		if(c=='M') change(l,r,w);//区间操作
		else cout<<query(l,r,w)<<"\n";//区间查询
	}
	
}

基础莫队算法

莫队算法=离线+暴力+分块

基础莫队算法用于不修改只查询的一类区间问题，复杂度为 O ( n n ) O(n\sqrt{n}) O(nn ​) 。

一次性存储所有询问，按照查询区间 左端点所在块序号排序，块相同再按 右端点排序。

ll n,m,a[N],tmp;
struct nod{//记录查询,用来排序
	int L,R,k;
}q[N];
ll t,sum[N],ans[N],pos[N];
bool cmp(nod a,nod b){//莫队排序
	if(pos[a.L]!=pos[b.L]) return pos[a.L]<pos[b.L];
	if(pos[a.L]&1) return a.R>b.R;//奇偶性优化
	return a.R<b.R;
}
void add(int x){sum[a[x]]++;if(sum[a[x]]==1) tmp++;}
void del(int x){sum[a[x]]--;if(sum[a[x]]==0) tmp--;}
void solve(){
	cin>>n;
	int block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];pos[i]=(i-1)/block+1;//记录对应块
	}
	cin>>m;
	for(int i=1;i<=m;i++){//记录查询
		cin>>q[i].L>>q[i].R;q[i].k=i;
	}
	sort(q+1,q+m+1,cmp);//查询排序
	int L=1,R=0;
	for(int i=1;i<=m;i++){//查询处理
		while(L<q[i].L) del(L++);
		while(R>q[i].R) del(R--);
		while(L>q[i].L) add(--L);
		while(R<q[i].R) add(++R);
		ans[q[i].k]=tmp;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}

带修改的莫队算法

如果只是简单的单点修改，也能使用莫队算法，但是复杂度为 O ( m n 2 / 3 ) O(mn^{2/3}) O(mn2/3)

树上莫队

SP10707 COT2 - Count on a tree II - 洛谷

将树转换成欧拉序变为一维数组。