分块入门

窝发现这个东西真的好厉害呀，窝就写个窝的入门笔记吧 前置知识：没有。 不过你学过数据结构更好，然后复杂度证明你需要会均值不等式 为了简单，我们默认询问次数与序列长度同级（要不然码Latex要搞到手软） ------------ 这篇文章有丶啥东西？ 1.入门分块的入门 2.入门膜队的入门 3.权值分块 4.用分块吊打树套树 5.现在我都还没学会的二次离线膜队 ------------ #### 1.入门分块的入门 分块是一种将暴力进行平衡的数据结构，一般用于序列操作题 可以理解为把序列分成许多块，维护每一块的信息，降低查询复杂度（可以通过合并块来实现），以及降低修改复杂度（维护的信息尽量简单） $Ex.1$ ： [【模板】树状数组 1](https://www.luogu.org/problemnew/show/P3374) 按照刚刚的说法，我们不如假设分成$T$块，则每块的大小就是$N / T$。 那维护什么信息呢？窝们要查询和那肯定维护和啊！ 所以不妨记原序列为$A$，$sum_i$代表第$i$块的和。对于每一个单点增加操作，为了正确维护信息，窝们可以让它所在块的$sum$增加$x$，然后原数组增加$x$，那么时间复杂度为$O(1)$。 而对于询问操作，窝们可以直接将询问分解成几个询问合并，由于可以在$O(1)$时间内求出每个块的和（直接查$sum$），那么窝们应当把询问分成完整的块与不完整的块，对于完整的块，最多有$T$个，查询他们的和是$O(T)$的，对于不完整的块，窝们在$A$数组上暴力，由于不完整的块最多两个（因为询问是一个连续序列然后如果有三个肯定能合并一个），时间复杂度为$O(N / T)$，总时间为$O(N / T + T)$。$N / T + T >= 2 \sqrt{N / T * T} =2\sqrt{N}$，且该式当且仅当$T = \sqrt{N}$取到最小值。 综上，询问时间复杂度$O( \sqrt{N} )$，修改时间复杂度$O(1)$ 看到这里你可能觉得这狗屁东西没什么用，给我树状数组复杂度吊着打而且树状数组还好写。 但就是因为这神奇的$O(1)$存在，接下来它将会成为许多题目的最优复杂度。 然后到第一节的最后，这里窝还想说说这一题的另一种分块解法，可以做到询问$O(1)$，修改$O(\sqrt{N})$。 分$\sqrt{N}$块，每块维护块内前缀和以及大块前缀和（即$pre1[i][j]$代表第$i$块前$j$个数的前缀和，$pre2[i]$代表第一个块到第$i$个块中包含的所有元素的和），然后修改的时候暴力改这两个数组，$O(\sqrt{N})$，查询的话查这两个表就好了，窝感觉泥萌这么神应该不用窝教怎么查了。 这两个东西这么好写你们随便写写我就不上$code$了 ------------ #### 2.入门膜队的入门 $Ex.2$：[【SDOI2009】HH的项链](https://www.luogu.org/problemnew/show/P1972) 考虑到窝们在学分块，所以假装不会主席树，所以要询问区间不同值，窝们可以先把询问给它离线下来。 窝们想下窝们需要什么，假设窝们能在每个询问得到这个询问所需要的区间的信息就好了。 考虑询问区间$[l1,r1] -> [l2,r2]$，有哪些变了，哪些没变。不妨假设$l1<l2$（不满足可以交换），所以区间减少了$[l1,l2 - 1]$这一段，那我们可以动态维护一个区间信息，只要出现区间左右指针变化，我们暴力维护就好了（指针向左/右移动一格），在这一题里，这个可以做到$O(1)$。 那么现在对于每一个询问我们都可以直接回答了，现在的目的是找到一种给询问排序的顺序，让指针移动次数尽量少。 最简单是按照左端点排序，但是这样不太对，虽然因为左指针只会动$N$次 ，但是你右指针最坏还是要走$N^2$次的，所以窝们得换种排序方式。 可以这么排，先把序列分$T$块，如果两个询问的左端点在同一个块里，则按照右端点排序，否则按照左端点位于的块排序。考虑左端点的移动次数，在同一个块里，最多存在$N / T$个左端点不同的询问，所以对于每一个块，左端点最多移动$N / T$次，一共$M$个询问，故左端点移动$N * M / T$次；对于右端点，每个块内是单调递增的，最坏会走$N$个数，故右端点移动$N * T$次。 总时间复杂度：$ N * M / T + N * T >= 2 \sqrt{N * M / T * N * T} = N * \sqrt{M}$，当且仅当$T = \sqrt{M}$取到最优复杂度$O(N * \sqrt{M})$。 ``` inline void add(int x) {if(!cx[x]) ++sum; ++cx[x];} inline void del(int x) {--cx[x]; if(!cx[x]) --sum;} void Mo_Algorithm() { int pos1 = 1 , pos2 = 0; for(int i = 0 ; i < (int)v.size() ; ++i) { while(pos1 > v[i].l) add(A[--pos1]); while(pos2 < v[i].r) add(A[++pos2]); while(pos1 < v[i].l) del(A[pos1++]); while(pos2 > v[i].r) del(A[pos2--]); ans[v[i].num] = sum; } } ``` code差不多长这个样，前提是你的**v**这个询问序列要按照刚刚说的排好序 $Ex.3$：[Gty的二逼妹子序列](https://www.luogu.org/problemnew/show/P4867) 这道题比刚刚那道多了一个区间限制，我们可以主席树套个平衡树。 但是这样写空间死鬼死鬼大，$O(N*log^2N)$，30Mb我觉得你GG 那我们可以搞膜队，膜队复杂度是线性（空间），十分适合这道题 那么窝们只需要把那个暴力更新的数组改成一个支持单点修改区间询问和的数据结构就好了。 树状数组？ 那时间复杂度是$O(N * \sqrt{N} * log N)$ 考虑到复杂度都是花在指针的移动上，应当让复杂度尽量小，而询问操作复杂度其实可以为所欲为（只要不超过$\sqrt{N}$）。 还记得上面的分块的复杂度嘛！ 窝们把这个树状数组换成分块，惊奇的是复杂度竟然降了！$O(N * \sqrt{N})$！ 所以这一题做完了，你只需要把上面的add，del，改成分块操作就好了。 所以说暴力应该配暴力，你用log数据结构是与分块不搭的。实在不会写Code的话可以看看人家题目下面的标程。 ------------ #### 3.我也不知道该把权值分块扔在哪里