分块学习笔记

简介

分块是什么？分块就是暴力！

相对于其它数据结构，其优点在于：因为其结构简单，能够轻松地维护更多种类的信息。但是相对的，其 理论复杂度 往往都是要更大的。

但是 ~~实际复杂度和理论复杂度没有关系~~ 分块常数小，很多时候不见得会跑得比其它数据结构慢。

我觉得，学习分块的最好办法就是做题。

Part 1 基础

首先，你要对普通的数列分块和值域分块比较熟练。

最简单的思想，就是将整个序列/值域分为 (sqrt n) 个块，每块大小相等。为什么是 (sqrt n)？实际上这个大小取决于具体题目，甚至可能大小不等。在基础的题目里面往往是 (sqrt n)，目的是让复杂度上界尽量低。

【模板】线段树 1

可以拿线段树的模板来锻炼一下数列分块。

Part 2 块内信息的多样化

块内的前缀后缀

除了整块的总和，实际上还有很多信息都是可以进行分块维护的，比如说块内的前缀后缀和，下面这道期望 (operatorname O(1)) RMQ 就需要用到这个东西。

由乃救爷爷

这是期望 (operatorname O(1)) RMQ 的板子，里面用到的思想非常地妙：处理出每个块内的前缀 (max)，后缀 (max)，以及若干个连续块的 (max)。

同一个块内的需要暴力算，其它都是 (operatorname O(1)) 的。因为数据随机，所以可以知道期望调用同一个块内的次数，可以得出复杂度依然是对的。

块内凸包

经常用于单点修，区间查，并且其式子可以斜优的题目。

时间管理

是我之前自己出的一道题目。简化版题意：单点修，查询排名和权值乘积的最大值（不太方便描述，建议看原题）。

Solution

Part 3 莫队

莫队的思路是：通过处理出的 ([l,r]) 的信息，暴力转移到 ([l+1,r],[l-1,r],[l,r-1],[l,r+1]) 这些地方。

我们先进行数列分块，对于询问 ([l,r])，把 (l) 在同一个块内的询问放在一起，然后按 (r) 升序排序。这样按顺序处理能保证转移次数是 (nsqrt n) 级别的。

[国家集训队]小Z的袜子

莫队的板题。

莫队还有很多可以深入下去的内容，可以去 oiwiki 上自行学习。

Part 4 根号分治

是一种思想，将询问或者修改进行分类讨论，根据其规模不同，采用不同的方法处理，达到复杂度均摊的效果。

[TJOI2007] 可爱的质数/【模板】BSGS

BSGS 就是经典的根号分治的运用，考虑将 (b^lequiv npmod p) 这个式子中的 (l) 写成 (xcdot lceil sqrt q ceil -y) 的形式，然后同乘 (b^y)，这样只需要分别枚举 (x) 和 (y)，而这两者的的范围都是根号的。

扩展 BSGS 就是多推一步式子，并不难。

到这里为止做一些练习巩固一下吧！

Part 5 常见的分块套路

第二分块

[Ynoi2018] 五彩斑斓的世界

( exttt{to be continue} o)

$$ exttt{Dirty Deeds Done Dirt Cheap}$$