几类分块
（以下均为学习了栋栋的根号算法之后的总结）
一类分块
这类分块还是比较简单的。
一般我们先确定一个阈值Threshold，一般是sqrt(n)。也就是说，我们每一个块的大小是sqrt(n)的。并且块的个数是sqrt(n)的。
先来看一下分块是怎么处理区间问题的。
例1-1：
6+9
题目描述
给出一个长度为N的区间。
现在给出M个操作：
Q l r：查询[l..r]区间内有多少个数由“6”或者“9”或者“6与9”组成。
A l r w：将[l..r]区间中所有的数加上w。
输入输出格式输入格式：
第一行是2个正整数，N与M。
第二行是N个正整数，描述原始的序列。
接下来M行，每行第一个字母为“Q”或者“A”，之后有2个或者3个正整数，表示参数。
输出格式：
对于所有的Q操作，输出答案。
输入输出样例
输入样例#1：
5 3
6 9 69 96 669
Q 1 5
A 1 5 1
Q 1 5
输出样例#1：
5 0
说明
N,M<=10^5
1<=l<=r<=N
0<=w<=10^4
保证初始序列以及操作后的序列所有的数A[i]均满足：0<=A[i]<=10^4
（注：原题为“4”、“7”、“4与7”。由于不会构造数据，改为了“6”、“9”、“6与9”）
个人解法：
（引自广东五校联考的第六场）
怎么处理？发现A[i]<=10^4。
于是在10^4内的仅有6与9组成的数只有30个。于是我们可以枚举这30个数，将问题转换为“区间加一个数w”与“区间查询有多少个w”。
树套树？第一棵树维护区间，第二棵树维护桶？绞尽脑汁想压位？
让我们分块。设阈值Threshold=sqrt(n)，一共有sqrt(n)个块。每个块维护一个桶与一个标记。
那么空间复杂度是O(A[i]*sqrt(n))=O(10^4*300)，是可以支持的。
那么怎么处理？
对于修改：
如果跨了整个块，那么这个块的Tag+=w。剩余部分，我们暴力修改，之后重构这个块。
跨块的修改是O(sqrt(n))，暴力修改与重构是O(sqrt(n))。
对于询问：
如果跨了整个块，那么就是查桶内w-Tag的位置有多少个数。剩余部分，我们先把l与r所在块的Tag下传（修改A数组），之后再重构一下l与r所在的块。接下来暴力扫描就可以了。
跨块是查询是O(sqrt(n))，重构与暴力扫描是O(sqrt(n))。
由此总的复杂度是O(msqrt(n))。
代码如下：
https://code.csdn.net/snippets/2027146
块维护桶是一个很好的方法，空间比树套树小得多，时间复杂度为差不到哪里去。
从上一个例子中，我们可以看见，我们在查询或者修改中，需要知道一整个块的信息，以及剩余部分的信息。剩余部分的答案往往需要重构块或者暴力扫描，时间复杂度取决于块的大小Threshold，而一整个块的信息我们要枚举块，时间复杂度取决于块的个数。
由此分块很重要的就是平衡块的大小与块的个数。这个思想在第二类分块中更为有用。
块维护标记是一个常用的技巧。很多区间+w的操作，都可以用标记实现O(sqrt(n))（一般也是这样）
例题1-2：
区间k小值
题目描述
给出一个长度为N的序列，与M个操作。
要求支持操作：
1 l r w：表示给[l..r]的区间加上w。
2 l r k：表示查询[l..r]的区间第k小的数。
输入输出格式输入格式：
第一行为两个正整数n与m。
接下来一行，共n个数，描述原始序列。
接下来m行，每行4个数，表示操作。
输出格式：
共m行，对于每一个2操作，输出答案。
输入输出样例
输入样例#1：
8 8
434 208 378 245 421 43 98 35
1 5 8 62
2 1 2 2
2 2 8 3
2 2 5 2
1 1 8 472
2 1 7 2
1 1 5 40
2 3 4 2
输出样例#1：
434
160
245
632
890
说明
N，M<=10^4
（原题数据范围M，N<=10^5，时限为7000ms）
个人解法：
区间k小？主席树？
然而带了区间+w的操作……主席树？我不会（不过看到BZOJ上说还是可以做的？）。
我们来说分块吧。
分块。每个块内维护加法标记是显然的。应该还要维护一个升序的数组。
对于修改：
有了上一个题的经验就很简单了。跨块的，标记+=w。剩余的的，暴力修改，重新排序。（这里带一个log(sqrt(n))的排序，不过似乎log(sqrt(n))没什么大的影响）
时间复杂度O(sqrt(n)*log(sqrt(n)))
对于查询：
记得一个二分最平均数的题来着？有这么一种方法，把查询第k小转换为二分判断问题。那么在这里，我们同样可以二分查找，之后查找小于或等于它的有多少个。
对于整个块的信息，我们可以二分查找有多少个小于或者等于w的数。对于不是整个块的，重构一下块与A数组，之后暴力扫描即可。
时间复杂度O(sqrt(n)*log(maxn))
细节问题：由于我们不知道这一段区间的数具体是哪一些，所以我们只能盲查。这样可能会有一个问题，就是我们最终查到的那个数可能不在这个区间内。由此如果找到最小一个数w，使得小于或者等于w的数有k个。这个w就是我们要找的第k小的数。
所以总的时间复杂度为O(m*sqrt(n)*log(maxn))
代码如下：
https://code.csdn.net/snippets/2036883
同样，块维护升序数组也是一个常用的手段。
接下来我们看到第二种分块。
块状链表
写过一遍不是很想写了
接下来是第三类分块。
在线莫队
虽然这是和在线莫队是有不同的，但是大体思路一致。暂且这么理解吧。
有一份在线莫队的报告，总结在莫队中。可以先看一下里面关于在线莫队求和的方法。
我们还是看一下“第三类分块”。
通常这一类分块是不支持修改的。一般是处理出关于块的答案Ans[i][j]，表示第i个块到第j个块的答案。同时处理出元素关于块的前缀信息Sum[i][j]，表示第i个元素在[1..j]的块中的信息。
例题3-2：
原题：https://www.lydsy.com/JudgeOnline/problem.php?id=4241
4241: 历史研究
Description
IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。
日记中记录了连续N天发生的时间，大约每天发生一件。
事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1.选择日记中连续的一些天作为分析的时间段
2.事件种类t的重要度为t*(这段时间内重要度为t的事件数)
3.计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
Input
第一行两个空格分隔的整数N和Q，表示日记一共记录了N天，询问有Q次。
接下来一行N个空格分隔的整数X1...XN，Xi表示第i天发生的事件的种类
接下来Q行，第i行(1<=i<=Q)有两个空格分隔整数Ai和Bi，表示第i次询问的区间为[Ai,Bi]。
Output
输出Q行，第i行(1<=i<=Q)一个整数，表示第i次询问的最大重要度
Sample Input
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
Sample Output
9
8
8
16
16
HINT
1<=N<=10^5
1<=Q<=10^5
1<=Xi<=10^9 (1<=i<=N)
个人解法：
我们要维护的是最大的“t*(这段区间内重要度为t的事件个数)”。就算是用分块，这个东西很不好维护。
但是没有修改。
于是我们可以考虑预处理。
我们分块之后，Sum[i][j]表示第i小的t，在前j个块中，出现的次数。这个可以O(nsqrt(n))处理出来。
接下来我们处理Ans[i][j]，Ans[i][j]直接维护我们需要的信息就好了。怎么维护呢？我们考虑到Ans[i][j]是可以由Ans[i][i]与Ans[i+1][j]维护得来。由此我们可以参考区间DP的思想。
Ans[i][j]=max{Ans[i][i],Ans[i+1][j],T[A[k]]*Times[A[k]]}，其中A[k]是第i个块中的元素，Times[A[k]]表示A[k]在[i..j]这段块中出现的次数。
这样我们就把块与块之间的答案处理出来了。
对于询问：
我们可以先找到Ans[pl+1][pr-1]（pl为l所在的块，pr为r所在的块），先作为答案。
之后枚举剩余部分的元素，用一个桶维护剩余部分的元素出现的次数，并且通过Sum得到它们在整个询问的区间中出现的次数，用t*Times来更新答案。
时间复杂度O(msqrt(n))。
细节问题：当然数字比较大，需要离散。
代码如下：
https://code.csdn.net/snippets/2043791
看上去不可做的题就这样被预处理干掉了。
之所以要预处理Ans[i][j]，是因为我们如果只有单个块的信息，我们不能迅速得出[i..j]这一段块所包含的区间的信息。
这个时候我们就通常可考虑通过预处理来实现。
如果强行需要修改怎么办？
发现，如果我们需要修改，那么我们可能需要重新构造Ans数组，花费时间代价极高。考虑到之前提及的在线莫队。
在线莫队是没有处理出Ans[i][j]的，这样使得它在查询的时候需要先扫描[pl+1..pr-1]的块来统计答案。但是对于修改，由于它没有和很多元素关联，是可以实现O(sqrt(n))的维护。
当然这类修改亦可以通过构造其他信息来维护。类似某锟上次出的一道位运算的题，不过构造这种玄学的东西……
笔者水平有限，故笔记至此结束。