首师大附中
正题
将一个集合划分成若干个规模较小的子集合，一般来说，我们倾向于把性质接近的元素分到同一个子集里面，并把每个子集的元素按照一定结构组织起来，形式主要有两种：
1.线形序列的分块化
2.树形结构的分块化
先讲讲现行序列的分块化。
线形序列预处理：在分好块之后，尝试对线性序列进行预处理。当查询任意区间的时候，对于预处理的部分直接返回结果。
我们将A序列分好块的时候我们可以维护一个数组P[i][j][信息]。这样的空间复杂度是O(n信息)。而且对于一些区间不满足加法的题目很有用。
例题1：给出一个N个数的序列，每个数位于1到N之间。M次询问，L R K ，每次询问区间[L,R]中恰好出现了K次的数字的数。
看到第一眼就很容易直接莫队秒掉。
为了锻炼分块，我们考虑分块。首先考虑根号分治，
的可以直接用一个空间复杂度为的复杂度把一个数出现的前缀和次数统计出来，然后每一次询问暴力统计就可以。
对于的，我们把序列分块，给每一块一个标号。
拿一个数组来记录从i块到j块中出现次数为q的数字个数。
再拿一个数组，表示前i个块中，q出现的次数。
然后对于一个区间，先把对应的提出来，然后在在向左和向右扩展的时候，我们看一下当前节点在i到j之间出现了多少次（可以通过op数组相减得到），然后修改A数组。同时增加op[j][当前的数]。因为这样就可以使得下次再次查询这个数的时候修改正确的A。
然后记录答案，最后还原P和op数组就可以了。
然后就是树结构的分块了。
这里只讲讲DFS分块。
这个DFS分块不是真的DFS序分块，因为真的DFS序分块可能会是的分到的块可能不是联通块。
DFS分块是这样分的。我们dfs遍历整棵树，经过一个节点的时候，先把这个节点压进栈内。当结束这个节点的子树时，若栈内子树元素个数>S时，我们把栈内子树元素个数弹出来并分块。
根据一个IOI2013的国家队论文，可以证明块总数时级别的。
树形结构的预处理：考虑设立若干个关键点，预处理出关键点对之间的路径信息。对于一个有根树，按照深度从大到小枚举树中的每个点，并判断是否将其标记为关键点，将点u标记为关键点当且仅当u的子树中存在一个点到点u的路径上没有关键点，且路径上点的数目大于S。这个操作可以用dfs完成，大概就是记录一下最远的非关键点是哪一个，然后在每一次选出关键点的时候，令距离为-1，再往上传就好了。
我们知道这个东西就可以维护许多树上路径操作了。因为我们可以预处理两两关键点之间的信息。但是预处理并不是那么简单的事情。因为在线性序列上，我们可以先处理长度为1的，然后可以通过合并得到长度为2的。。。
具体怎么预处理两两关键点之间的信息明天再问问老师，今天问老师，老师说回去找一找。
经典例题就是WC 2013的糖果公园了。
最后的最后，剩下的就是分块+离线了（也就是常常说的莫队算法了
这个相信大家都是会的，在这里就不在赘述了。
相关阅读
题目链接：【清华集训 2014】玛里苟斯 推荐博客：【BZOJ 3811】玛里苟斯：线性基（详细证明） 首先想到将k" role="presentation" style="po