适用情况:对于序列A中某个子区间的问题,当遇到像众数类似的不满足区间合并的性质的数据,或者一些用线段树、树状数组比较难维护的数据时,使用分块莫队。
实际上是对暴力的一种优化,形式多灵活,是骗分小帮手
- 分块
思想:”把序列分成一些块,对于每个块打标记,使得对于每个块我们可以在指定复杂度内完成操作。于是我们可以将所有符合要求的整块处理掉(不会太多),再暴力处理不被完全包含的角块(不会太大),从而在有限时间内完成操作“
复杂度:详细可以见dalao分块入门 - guoshaoyang - 博客园 (cnblogs.com)
根号平衡 :
A. 敌兵布阵 oj上没有数据,咕了
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
B. Bounce 弹飞绵羊
维护每一个装置从当前块跳到下一块的步数和位置
每次修改pos,暴力修改当前块首到pos的值
相当于优化了原来一个一个跳的暴力
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
C. 蒲公英
预处理任意两个快之间的众数,数字出现的前缀和,然后每次从上面结论中找答案
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
D. 教主的魔法 板子题
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
- 莫队
思路,通过将排序进行适当的排列,每次通过动态指针维护l,r区间
下课了,晚上看电影时补全
标签:暴力,分块,复杂度,pos,笔记,众数,莫队 From: https://www.cnblogs.com/limingyun/p/17111818.html