浅析[分块]qwq
首先说明这篇博客写得奇差无比
让我们理清一下为什么要打分块,在大部分情况下,线段树啊,splay,treap,主席树什么的都要比分块的效率高得多,但是在出问题的时候如果你和这些数据结构只是混的脸熟的话,一旦错误可能就会导致心态崩溃,而且调试困难(大佬:很轻松啊....)所以,分块是一个时间效率不是很高的,代码量也不是很高的数据结构,水分是可以的,在全场都是30分的情况下,你能用分块水到个60,70就是胜利,所以分块很多时候也是和STL一起用的,达到(nlogn√n)的效果吧。
原理
把一段数列1...n分成√n块,如果√n*√n<n,n++。这样能保证每一块的大小都<=√n,我不会证明,但是此时时间复杂度一般为(n√n),就可以开始水分了。
比如,在我们要解决一段100000左右的序列时,最简单的询问 (l,r)求和 给(l,r)加上一个值。
大佬A:线段树@#@@¥%@!#(啪)
大佬B:平衡树%¥……¥#%@@(啪)
大佬C:树套树@¥%@#%#……(啪)
那么身为蒟蒻的我:分块!(瑟瑟发抖)
首先让我们来讲一讲分块是什么
分块,我这里只是简单的把一段数,放到几个块里面,怎么放呢,按照某个大佬的证明,把每连续的√n个数放在一个块里的时间复杂度一般是最优的,当然有时候√n并不是最优解。
那么要怎么分呢?
首先,我们让int tmp=sqrt(n),这样就可以保证有√n块,然后如果有任何一块处于(l,r)之间,就给这个块打上标记进行操作,这样肯定是有可能会有 l和r 处在两个块中的,而且我们也不能对那两的块直接修改,就暴力修改块里面的内容。即每一次的时间复杂度大概为(3√n)。
所以我们就是要预先处理好每一块的内容,预处理大概是(n√n)的,查询大概是(1)的。
大概的建块过程如下
void build()
{
num=tmp;if(tmp*tmp<n)num++; //因为int向下取整,所以有可能tmp*tmp<n,存不了那么多的数
for(int i=;i<=num;i++)
{
l[i]=num*(i-)+;r[i]=num*i; //每一个块的左右区间
}
r[num]=n;
int s= ;
for (int i=;i<=n;i++) {if (i>r[s]) s++; belong[i]=s;} //处理出每一个数所属于的块
//...
//你要预处理的内容
}
然后查询跟上面也差不多,因题目而异。
下面贴一个静态查询最大值的代码
int query(int x,int y)
{
int ans=-;
if(belong[x]==belong[y])//在一个块内就直接暴力统计
{
for(int i=x;i<=y;i++)
ans=max(ans,ch[i]);
return ans;
}
for(int i=x;i<=r[belong[x]];i++)//统计最左边的块的情况
ans=max(ans,ch[i]);
for(int i=belong[x]+;i<=belong[y]-;i++)//中间的先于预处理好,然后每一块的情况O(1)查询
ans=max(ans,maxx[i]);
for(int i=l[belong[y]];i<=y;i++)//统计最右边的块的情况
ans=max(ans,ch[i]);
return ans;
}
所以原理大概就讲到这里吧。
现在通过一些简单的例题入门吧。
1.教主的魔法
3.哈希冲突
4.作诗
1.教主的魔法
做法分析:
分块+排序+二分
首先我们把这个题目拆开来看:
(1)要询问或给(l,r)加一个值
(2)在(l,r)区间的值是不定值,还要求的是大于等于k的数有多少
由(1)–>得尝试分块和分块的加法标记
由(2)–>得我们可以事先处理好每一块的顺序,然后找到大于等于k的第一个数,就能求出每一块的贡献值了–>sort+vector
要注意的是,当l,r处在两个不完整的块,暴力加上在排序就ok了
祝大佬AC愉快23333333
2.弹飞绵羊
做法分析:
不属于hzw的入门分块练习
这里需要我们处理出每一块中,进入某个点后,会进入下一个块的哪一个点,需要几次才能弹出块,修改时记得同时修改相应块的内容。
靠大佬自己思维了。
3.哈希冲突
做法分析:
(sqrt(),不只是分块)
(1)首先,我们先处理出sqrt()内的模数池的值,这样询问就只要o(1),预处理o(n√n)。
(2)其次,当模数大于sqrt()时,我们暴力一次的代价为o(√n)
4.作诗
做法分析:
1.我们考虑一下分块的话要每一块都保存是正偶数的数字的个数,用一个ans[i][j]保存第i块到第j块内符合条件的数字的个数,o(1)的查询,前缀和的思想
2.在最左端的最右端的用一个统计数组暴力即可
3.但是要记住最左端和最右端的数字要与整个[l,r]区间相关联,所以用一个sum[i][j]保存第[i]块第[j]种颜色的数量
5.蒲公英
做法分析:
排序+离散化+二分+区间预处理+分块
(1)读入的每一个值超过一个数组下标可以统计的范围–>离散化
(2)求众数==教主的魔法(2)的思想–>sort+vector
(3)为了更加优化时间复杂度,我们事先处理好[l,r]里面经过块的众数,然后暴力vector不完整块的中可能的众数–>区间预处理
分块qwq蒟蒻我已经没什么能教的了,大佬AK比赛愉快。
ps:(最后推荐一下黄学长的分块,大概是所有分块里面教的最好的了)「分块」数列分块入门1 – 9 by hzwer
最新文章
- Windows环境安装Linux系统及JDK部署
- URL Scheme APP跳转safari以及跳回APP
- JavaScript基础知识点
- 【Reporting Services 报表开发】— 级联式参数设置
- Linux下librdkafka客户端的编译运行
- Bzoj 1976: [BeiJing2010组队]能量魔方 Cube 最小割,最大流
- ES6笔记① var 和 let的区别
- Maven基本安装与配置
- Python基础学习篇章三
- HQL: The Hibernate Query Language
- 数据传输流程和socket简单操作
- stark组件数据库管理软件的总结
- LAMP编译安装部分
- Redis实战总结-配置、持久化、复制
- Objective-c:NSFileHandle类,创建流对象,对文件进行写入、读取的操作
- Checkpoint的运行原理和源码实现
- Seaborn-05-Pairplot多变量图
- APUE学习笔记——10.18 system函数 与waitpid
- JS高程3:DOM-DOM操作技术
- hdu 2117:Just a Numble(水题,模拟除法运算)
热门文章
- Django(part2)
- SpringMVC(三) RESTful架构和文件上传下载
- python 时间差计算
- MySQL本地密码过期处理及永不过期设置
- 并发设计模式之Guarded Suspension模式
- 详解JavaScript中的原型和继承-转自颜海镜大大
- Vue学习之v-if与v-show的区别
- luogu P1405 苦恼的小明(欧拉定理)
- MySQL中将数据库表名修改成大写的存储过程
- 错误解决:error: expected ‘;’, ‘,’ or ‘)’ before ‘&;’ token