首页 > 编程语言 >算法笔记(6)数列分块

算法笔记(6)数列分块

时间:2023-10-23 18:22:25浏览次数:38  
标签:数列 分块 int 复杂度 pos sqrt 算法

原发表于我的博客

前言

分块不能说是一种数据结构,它是一种思想,无论是数列分块,块状链表,还是数论分块,莫队算法,都应用了分块的思想。

本文主要介绍狭义上的分块,即数列分块。

数列分块的引入

数列分块可以说是暴力,一种优美的暴力,它的基本思路是,把数列分成若干块(一般取\(\sqrt n\)),分块预处理。

块内预处理

在修改时,块内直接修改标记(别告诉我你不会线段树),块外暴力修改(同时更新数据)

同理,查询时块内直接看预处理的数据和标记,块外(边角料)暴力。

分块修改

数列分块的复杂度是\(O(n\sqrt n)\),肯定比线段树或树状数组的\(O(n\log n)\)要慢,但是它容易写,而且直观,可以解决一些线段树无法维护的问题,在复杂度允许的情况下可以使用。

数列分块复杂度证明(可跳过)

设对数列分成\(T\)块。

最坏情况下需要修改\(S_1< T\)块。

块外最坏情况下需要修改\(S_2<\frac{2n}{T}\)个元素。

整体操作\(\le S_1+S_2\)次。

由均值不等式,

\[\frac{S_1+S_2}{2} \le \sqrt {S_1S_2} \]

\[S_1+S_2 \le 2 \sqrt {T \times \frac{2n}{T}} \]

故数列分块单次操作最坏情况下小于

\[2 \sqrt {2n} \]

忽略常数,则数列分块总体复杂度为

\[q \sqrt n \]

若\(q\),\(n\)同阶,则时间复杂度为

\[O(n\sqrt n) \]

注:刚学均值不等式没几天,证明的可能不对,如果有错误请评论或私信我指出。

代码详解

loj. 数列分块入门1为例。

预处理

在预处理中,会处理以下几个变量。

R,L代表每一个块的左右边界(其实可以不处理这个,但是写起来比较麻烦)

pos保存着每一个数所在的块。

int t=sqrt(n);//分t个块
for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;//处理出每个块的左右边界
if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;//分块后最后一部分很可能不在块内,所以要增加一个块
for(int i=1;i<=t;i++)
	for(int j=L[i];j<=R[i];j++) pos[j]=i;//处理出每个数所在块的编号

注意,分块后最后一部分很可能不在块内,所以要增加一个块。

这个预处理的时间复杂度为\(O(n)\)。

修改

修改操作采用的是”块内修改标记,块外暴力修改“的策略。

void change(int l,int r,int k){
	int p=pos[l],q=pos[r];//找到左右边界所在的块
	if(p==q){
		//如果这个区间在一个块内,就直接暴力修改
		for(int i=l;i<=r;i++) a[i]+=k;
	}
	else{
		for(int i=l;i<=R[p];i++) a[i]+=k;//整块左边的”边角料“,暴力修改
		for(int i=p+1;i<=q-1;i++) add[i]+=k;//对于整块,直接修改标记
		for(int i=L[q];i<=r;i++) a[i]+=k;//整块右边的”边角料“
	}
}

这就是分块的基本操作,接下来看几道例题。

例题

数列分块入门 2

原题

最开始看到这题,我以为是树套树,后来老师讲解才发现,分块真™暴力。

题意:区间加法,询问区间内小于某个值\(x\)的元素个数。

分析:这题看起来很难,实际上直接查询操作直接暴力枚举即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int a[N],L[N],R[N],add[N],pos[N];
int n;
void change(int l,int r,int k){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(int i=l;i<=r;i++) a[i]+=k;
	}
	else{
		for(int i=l;i<=R[p];i++) a[i]+=k;
		for(int i=p+1;i<=q-1;i++) add[i]+=k;
		for(int i=L[q];i<=r;i++) a[i]+=k;
	}
}
int query(int l,int r,int k){
	int cnt=0;
	for(int i=l;i<=r;i++){
		if(a[i]+add[pos[i]]<k*k) cnt++;
	}
	return cnt;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
	for(int i=1;i<=t;i++)
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
	for(int i=1;i<=n;i++){
		int opt,l,r,k;
		scanf("%d%d%d%d",&opt,&l,&r,&k);
		if(opt) printf("%d\n",query(l,r,k));
		else change(l,r,k);
	}
}

数列分块入门 3

原题

题意:区间加法,询问区间内小于某个值\(x\)的前驱(比其小的最大元素)。

分析:

考虑每个块建一个vector,块内排序,每次散块修改就重构,复杂度大概是预处理\(O(n\log n)\),散块重构:散块不超过\(2 \sqrt n\),共\(O(n\sqrt n\log n)\),访问前驱:散块直接暴力,整块每块内用lower_bound函数找,共\(O(n\sqrt n\log n)\),总复杂度\(O(n\sqrt n\log n)\)。

另一种做法是用set维护,预处理插入进set复杂度是\(O(n\log n)\),散块直接删除再插入,复杂度也是\(O(n\sqrt n\log n)\),访问前驱也是散块暴力,整块lower_bound,总复杂度两种方法相同,都是\(O(n\sqrt n\log n)\)。

我的代码使用了set,毕竟自动排序常数可能小点?(雾)

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,inf=0x3f3f3f3f;
int a[N],L[N],R[N],add[N],pos[N];
set<int>s[N];
int n;
void change(int l,int r,int k){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(int i=l;i<=r;i++){
			s[pos[i]].erase(a[i]);
			a[i]+=k;
			s[pos[i]].insert(a[i]);
		}
	}
	else{
		for(int i=l;i<=R[p];i++){
			s[pos[i]].erase(a[i]);
			a[i]+=k;
			s[pos[i]].insert(a[i]);
		}
		for(int i=p+1;i<=q-1;i++) add[i]+=k;
		for(int i=L[q];i<=r;i++){
			s[pos[i]].erase(a[i]);
			a[i]+=k;
			s[pos[i]].insert(a[i]);
		}
	}
}
int query(int l,int r,int k){
	int p=pos[l],q=pos[r],ans=-1;
	if(p==q){
		for(int i=l;i<=r;i++){
			if(a[i]+add[pos[i]]<k) ans=max(ans,a[i]+add[pos[i]]);
		}
	}
	else{
		for(int i=l;i<=R[p];i++){
			if(a[i]+add[pos[i]]<k) ans=max(ans,a[i]+add[pos[i]]);
		}
		for(int i=p+1;i<=q-1;i++){
			int d=k-add[i];
			auto it=s[i].lower_bound(d);
			if(it==s[i].begin()) continue;
			it--;
			ans=max(ans,*it+add[i]);
		}
		for(int i=L[q];i<=r;i++){
			if(a[i]+add[pos[i]]<k) ans=max(ans,a[i]+add[pos[i]]);
		}
	}
	return ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
	for(int i=1;i<=t;i++){
		s[i].insert(-1);
		for(int j=L[i];j<=R[i];j++) pos[j]=i,s[i].insert(a[j]);
	}
	for(int i=1;i<=n;i++){
		int opt,l,r,k;
		scanf("%d%d%d%d",&opt,&l,&r,&k);
		if(opt) printf("%d\n",query(l,r,k));
		else change(l,r,k);
	}
}

数列分块入门 4

原题

题意:区间加法,区间求和。

分析:多维护一个数组sum,表示这个块的和,修改时散块也更新sum,整块也更新sum。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+10;
int a[N],L[N],R[N],add[N],pos[N],sum[N];
int n;
void change(int l,int r,int k){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(int i=l;i<=r;i++) a[i]+=k,sum[pos[i]]+=k;
	}
	else{
		for(int i=l;i<=R[p];i++) a[i]+=k,sum[pos[i]]+=k;
		for(int i=p+1;i<=q-1;i++) add[i]+=k,sum[i]+=(R[i]-L[i]+1)*k;
		for(int i=L[q];i<=r;i++) a[i]+=k,sum[pos[i]]+=k;
	}
}
int query(int l,int r){
	int p=pos[l],q=pos[r],ans=0;
	if(p==q){
		for(int i=l;i<=r;i++) ans+=a[i]+add[pos[i]];
	}
	else{
		for(int i=l;i<=R[p];i++) ans+=a[i]+add[pos[i]];
		for(int i=p+1;i<=q-1;i++) ans+=sum[i];
		for(int i=L[q];i<=r;i++) ans+=a[i]+add[pos[i]];
	}	
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
	for(int i=1;i<=t;i++){
		sum[i]=add[i]=0;
		for(int j=L[i];j<=R[i];j++) pos[j]=i,sum[i]+=a[j];
	}
	for(int i=1;i<=n;i++){
		int opt,l,r,k;
		cin>>opt>>l>>r>>k;
		if(opt) cout<<query(l,r)%(k+1)<<endl;
		else change(l,r,k);
	}
}

习题

  1. loj上分块入门5--9
  2. ynoi大分块

标签:数列,分块,int,复杂度,pos,sqrt,算法
From: https://www.cnblogs.com/luhaoren/p/fenkuai.html

相关文章

  • 算法笔记(2)FHQtreap
    原发布于我的个人博客前言FHQtreap绝对是平衡树里最好写,最实用的,他几乎能做所有splay或其它平衡树能做的事,还能可持久化!这篇文章将会介绍FHQtreap的基本操作和维护区间的操作,并附上例题。基本操作FHQtreap的基本操作只有两个,分裂和合并。有些读者可能会问,分裂和合并和平衡树......
  • K-medoids聚类算法
    发展:们每次选簇的平均值作为新的中心,迭代直到簇中对象分布不再变化。因此一个具有很大极端值的对象会扭曲数据分布,造成算法对极端值敏感在聚类分析中,异常值通常会引起问题,因为它们可能会被分配到一个独立的聚类,从而干扰正常的聚类结果。这可能导致聚类算法产生不合理或不稳定的......
  • 算法笔记(1)线段树
    原发表于个人博客。前言线段树,是数据结构皇冠上的明珠(我编的)。它用途广泛,被一代代的oier应用,改进,优化。本文介绍了线段树的基础知识和各种拓展(包括权值线段树,可持久化线段树),各种优化方式(包括zkw线段树,动态开点,离散化),希望能帮到更多的oier。在学习线段树前,默认你应该学会一下......
  • 算法-共识算法
    一、Paxos    基础的Paxos算法包括如下三种:BasicPaxos、MultiPaxos、FastPaxos     Paxos将系统中的角色分为提议者(Proposer),决策者(Acceptor),和最终决策学习者(Learner):    【Proposer】:提出提案(Proposal)。Proposal信息包括提案编号(ProposalID)......
  • C++U4-贪心算法1
    本节学习目标:贪心算法的概念以及对应练习题 贪心算法概念贪心算法的特点 利用贪心算法的两个性质 练习1:最优装载问题  【本题算法分析】优先把重量小的物品放进去,在容量固定的情况下,装的物品量最多。因此采用重量最轻者先装的贪心选择策略,可从局部最优达到......
  • 文心一言 VS 讯飞星火 VS chatgpt (119)-- 算法导论10.3 4题
    四、用go语言,我们往往希望双向链表的所有元素在存储器中保持紧凑,例如,在多数组表示中占用前m个下标位置。(在页式虚拟存储的计算环境下,即为这种情况。)假设除指向链表本身的指针外没有其他指针指向该链表的元素,试说明如何实现过程ALLOCATE-OBIECT和FREE-OBJECT,使得该表示保持紧凑......
  • 区间加等比数列
    https://www.luogu.com.cn/problem/U329489给出一个长度为n的数列接下来进行m次操作1lrkai=l~rA[i]+=k*a^(i-l)2lrkai=l~rsumA[i]*k*a^(i-l)最后输出一遍整个序列输出对998244353取模n,m<=1e5,5s操作分块+序列分块首先假设每B次操作......
  • 图书推荐与管理系统Python+协同过滤推荐算法+Django网页界面
    一、介绍图书管理与推荐系统。使用Python作为主要开发语言。前端采用HTML、CSS、BootStrap等技术搭建界面结构,后端采用Django作为逻辑处理,通过Ajax等技术实现数据交互通信。在图书推荐方面使用经典的协同过滤算法作为推荐算法模块。主要功能有:角色分为普通用户和管理员普通用户可注......
  • 磁盘调度算法
    1、FCFS调度--先来先服务例如,I/O请求块的柱面的顺序如下:98,183,37,122,14,124,65,67他请求的话,是这样一个图示:就直接根据请求序列进行调度即可,但是吧,它看起来摆动幅度就很大,这样导致这种形式的调度的性能比较差;2、SSTF调度--最短寻道时间优先还是按照上面那个请求序列:98,183......
  • 图书推荐管理系统Python+Django网页界面+协同过滤推荐算法
    一、介绍图书管理与推荐系统。使用Python作为主要开发语言。前端采用HTML、CSS、BootStrap等技术搭建界面结构,后端采用Django作为逻辑处理,通过Ajax等技术实现数据交互通信。在图书推荐方面使用经典的协同过滤算法作为推荐算法模块。主要功能有:角色分为普通用户和管理员普通用......