数据结构

· · 个人记录

分块

以前我对分块知之甚少，但其实分块中充分体现着人类智慧，用几道题记录一些常见 trick。

面试的考验[JSOI]

此题有双 log 离线做法，不说。

这题的分块做法我认为最智慧的地方就是，这些题总是有一些很显然的 n\sqrt nlogn 的做法，但是你用一些很巧妙的手段把 \operatorname{log} 消掉了。

按照我以前对分块的理解，分块应该是把一维的一坨东西分块，然后每个块里面与处理一些东西，询问的时候一个块一个块跳，再把边界的处理一下。 但是这题的做法为我开启了分块的大门，idea 来自题解。

分块还有一种常见预处理做法，就是预处理出每一个块到另一个块的连续段的贡献，由于组合最多 {\sqrt n}^2 即 n 种，所以复杂度和空间都是合法的。于是此题我们只需要再预处理出每一个点到每一段块的答案，然后再处理两边的零碎之间产生的贡献即可。

首先块内排序，这样我们就可以按照大小取出两边零碎的东西，这里的消 log 操作非常聪明！ 于是统计这一部分的答案是严格 n\sqrt n 的。

然后考虑先处理每个点到每一段块（是指从与这个点相邻的块一直连续到某一个块）的贡献，我们发现一共有 n\sqrt n 种组合，如果一个一个计算答案肯定是不行的于是这里有了一个非常聪明的办法，就是同时预处理一个块内的答案。

设我们现在要处理第 i 个块内每一个点到第 j 个块的答案，首先肯定是把到第 j-1（或 j+1）的答案取一下 min。对于 i 块中的每一个元素能与他产生最优贡献的一定是 j 块中与它值最接近的，我们直接在两个块排完序以后的数组中遍历，然后更新答案即可。真的非常聪明，消掉 \operatorname{log}。

然后我们处理块到块的答案。我们可以用刚才处理出来的这个数组进行统计，这个次序也超级巧妙啊，这里我们只需要暴力更新即可。

Yuno loves sqrt technology III

这题有两种分块做法，不过 lxl 卡掉了一种常数小空间大的做法（可以在 P4168 中提交），虽然有了上题的经验，但我还是被这两种人类智慧惊艳到了。

还是要预处理每个块到每个块的众数（及其出现次数），然后我们就看两边零散的这些数能否通过零散出现超过块间众数的出现次数。

空间大的做法：前缀和！ 为什么我没有想到呢。 处理出来每个数字在前几个块中的出现次数即可！空间 n\sqrt n。

更智慧的做法：用一个 vector 记录下每一个值出现的各个位置，然后！我们暴力更新答案！因为边上的零散内容最多出现 2\sqrt n 次，所以我们在取完块间答案后，众数的出现次数最多增多这么多，然后我们直接暴力遍历零散内容，肯定可以 O(1) 查询到它在 vector 中的下标对吧，然后我们只需要看它在 vector 中往前（或往后） ans 个的位置是否在询问的区间范围内即可，如果是就把答案加一。于是空间被优化成线性！

类似题目：作诗。

游戏王

洛谷民间比赛的分治+分块好题。数论分块之类的思想，以前没遇到过，很巧妙！

首先看到这种乘积限制的题目就应该考虑到这种做法。我们会发现如果 \lfloor\frac m i\rfloor=\lfloor \frac m j\rfloor，那么 i 和 j 的效果就是相同的。也就是说他们俩可以当成一类的。那么总共的类数的规模就在 2\sqrt V 以内，于是我们的体积就被优化到了根号级别。为什么是这个范围（这个证明有点抽象）：对于 i\le \sqrt n，\lfloor n/i \rfloor 最多 \sqrt n 种，而对于 i>\sqrt n ，因为 \lfloor n/i \rfloor \le \sqrt n，所以也最多 \sqrt n 种。

// 加点题外话，去 wiki 上查了一下数论分块，有一个结论。对于一个数字 i 所在的块的右端点是 \lfloor \frac n {\lfloor \frac n i\rfloor}\rfloor，这个结论其实比较显然。

这个题的分治也非常巧妙。由于每次查询的是某一段区间的答案，加上我们已经有根号级的基数，暴力或回滚莫队之类的显然不行。于是就有了分治做法！分治后求出从分治中心向两边延伸的前缀和（后缀和），然后对于跨过中心的询问处理，算出把其对应的两半合并到 V 处时的最大值，总复杂度 O((n\log n+q)\sqrt V)。话说为啥我写的跑得那么慢啊。

众数[ZJOI]

根号分治神题。

Wei 老师提示我们。看到出现次数应该考虑根号分治。这个题目要我们做的是在序列中选出一段区间，然后求这段区间的众数加上区间外众数的最大值。

按照出现次数根号分治。对于出现次数大于 \sqrt n 的颜色，最多不超过 \sqrt n 种，暴力枚举每一种，然后再暴力每一种另外的颜色，然后再用前缀和计算答案，要分在内和在外的讨论，很麻烦。这个相当于线性地求最大子段和，由于我们只需要枚举另外一种颜色的下标，所以对于一个出现次数大的数扫的总复杂度是线性。于是这一部分是 n\sqrt n。

然后考虑出现次数小的数之间的答案。这个实际上我们只需要考虑一种颜色在内或在外（其中一种）的情况即可，因为另一种情况会被别的颜色考虑到。这半部分我们需要考虑另一种做法了。我想的是计算在外面的答案，这样也好更新最终答案有哪些。我们把其它的颜色综合起来考虑，对于考虑的这个颜色，枚举左端点和右端点（复杂度是这个颜色出现次数的平方），然后查询这个区间里的众数就好了。

至于怎么处理区间众数，我们得考虑另一个性质。由于我们现在考虑的是小数之间的答案，所以这个众数也一定是在 \sqrt n 之内的。我们可以预处理出每一个左端点，众数为 j（j<=\sqrt n）时的最短右端点，这个预处理也用枚举颜色的方式。这样我们就可以处理前面的区间众数的询问了，根据我们枚举区间的方式，当固定一个左端点时，向右扩展右端点，那么区间众数肯定只增不减，于是暴力更新众数即可。

最后这一半的复杂度是 每种颜色出现次数小于等于 \sqrt n 的出现次数的平方和+ （每种颜色出现次数小的数的出现次数之和 \times \sqrt n），后半部分肯定最坏是 n\sqrt n，只需考虑前半部分的复杂度。我们考虑因为 a^2+b^2<=(a+b)^2，所以只有当每个小数出现的次数越多时越劣，就是剩下的小数都出现了 \sqrt n 次，总共 \sqrt n 个小数时复杂度最高，总复杂度也就是 n\sqrt n。

实现起来非常麻烦，很好很好的题。贴下代码

我突然发现好像江浙还挺喜欢考分块的，这题评黑绝不过分

[HNOI2010] 弹飞绵羊

图论题居然也能分块。这是一个 lct 的板子，建图方式显然，但我不会 lct。分块很奇妙。分块后维护每个点第一次跳出这个块的位置即可，过于巧妙。

带修区间 mex

揉合了很多 trick，非常非常聪明的 n\sqrt n做法，挂 tzc 博客。

分治

The Number of Subpermutations

好题。题解区有人在星战前夕预言异或哈希可能将流传开来。

这题难点不在哈希，原根哈希，异或哈希，或者各种乱搞哈希应该都能过。有很优雅的线性做法，但我重点想说的是分治做法（主要是我不会这种做法）。

考虑枚举区间的最大值。然后我们按照最大值分治，设这个最大值是 mx，以这个值为最大值的区间长度也一定是 mx，并且包含这个最大值本身。所以我们可以选取最大值分开的两块中较短的一块，遍历，然后判断以这个点为左端点或右端点长度为 mx 的区间是否合法，然后再递归两半即可。由于我们取的是较短的一边，所以其复杂度严格小于等于 n\log n。

很巧妙的一种分治方法。

寒假作业

简单题，很经典的分治。但是我想了十多分钟。 首先 k 没啥意义，可以直接把每个点的权值减 k，然后问题变成询问有多少个连续子段和大于 0。考虑了很多做法。但我认定这是一个分治，没想出来单 log 的做法。

分治，然后计算分治中心左边的后缀和，排序，再枚举右边的前缀和，二分查找个数。

莫队

简单回顾一下板子。

普通莫队 注意加奇偶排序优化常数，证明过于简单。

带修莫队 按照前两维所在块排序，第三维从小到大即可。块长取 n^{2/3}，总复杂度 n^{5/3} ，应该很难跑满，真是很优雅的暴力。

证明：设块长为 k，每一组询问的三维坐标为 (l,r,t)，假设 n、q 同阶。则显然 l 和 r 最多移动 nk 次，然后对于 l 和 r 它们所在块的情况最多有 {(\frac n k)}^2 种，然后在每种内 t 又最多会移动 n 次。于是总复杂度就会变成 O(2nk+{(\frac n k)}^2n) 我们发现块长取根号反而会退化为暴力。通过简单数学计算即可得到优雅暴力块长 n^{2/3}。

树上莫队 把树用欧拉序转成一维的东西，然后按普通莫队做即可，注意统计贡献时只统计出现次数为奇数次的即可。

回滚莫队 算是对普通莫队的优化，就是有一些题不方便加或删，每次强行把左端点所在块暴力处理即可，注意右端点的排序方式有对应要求，不能奇偶排序。

RMQ

经验的积累还是得靠刷题啊。

RMQ 有很多非常聪明的利用。

NOI2010超级钢琴

求最大的 k 个不完全重合的子段和，同时限制其长度范围。将子段和的计算转换为前缀和的相减，我们考虑怎么先取当前的最大值，以任意一个点 s 为起点，那么右端点就在 [s+L-1,s+R-1] 之间我们只需要取其中前缀和的最大值即可，因为都是要再剪掉 sum[s-1] ，这个就可以用 ST 表来维护了，于是我们用一个堆维护最大值，每次取完最大值以后，就把这个区间裂成两半，分别塞到堆里面，就可以了。

线段树

线段树合并/分裂

线段树合并单次最坏 O(n)，一般好像都是树上的合并，均摊单次是 log 的。线段树分裂是稳定单 log 的。

一些 trick

排序

学到了一个 trick，给一段区间排序可以转化为给一段 01 串排序。01 串排序用线段树维护可以做到 \log n，于是二分答案即可。话说这题是不是可以多此询问，整体二分。

[NOIP2022] 比赛

NOIP2023 前夕，终于把这个题补了。扫描线是一个应用广泛的经典 trick。

先说一种部分分做法，感觉这个比较容易理解。没扫描线那么抽象。

记录下每个点之前第一个比它大的值的位置，可以用单调栈做到线性，记为 pre，再记 A_q=max_{i=p}^qa_i，B_q 同理。

我们在区间 [l,r] 中枚举 q，我们考虑贡献，那么对于 p 在 pre_q 之后的位置时 A_q=a_q，再往前以此类推。那么我们只需要用线段树维护 A,B,A\times B 的值，区间修改，区间查询即可，复杂度 O(nm\log n)。

然后我们把这个问题转化成线段树维护历史版本和。

我们发现当我们从 1 到 n 遍历 q 的话，此时 q 对应的线段树与查询时的 l 时无关的，假设当前 q 扫到了一个位置，那么它就对于每一个 r>=q 的询问贡献一个 ask(l,r) 的值（这里的 ask 指线段树的参数）。而对于 l>q 的询问，显然线段树会返回 0，答案是正确的。

这就相当于我们对于每一个询问 r，询问所有 q<=r 时线段树上 ask(l,r) 的和，也就是历史版本和。

维护区间历史版本和的一种常规做法是开一个辅助数组。

对于普通区间加减的线段树，我们设一个节点的值是 A_i，历史版本和是 B_i，再设一个辅助数组 C_i=B_i-t\times A_i，t 是时间。我们发现对于区间加减没有影响到的地方 C 的值没变，而对于区间加了 x 的地方，设之前的 B_i=oB_i，之前的 C_i=oC_i，那么 C_i=oB_i+(A_i+x)-(t+1)(A_i+x)=oC_i-tx，也就是说相当于给 C 区间加减即可。

另一种做法就是硬维护标记，记一下最后一次更新的时间，然后区间加的时候，记录一下标记的累计值，标记乘时间的累计值，每次更新的时候就让标记乘时间的累计值加上标记累计值乘时间差，然后标记累计值直接维护即可。标记不下传，直接永久化，询问的时候输出区间和乘时间加上标记乘时间的累计值。

对于这个题我们可以类似地处理。

两种方法都可做，我选用第二种。如果区间赋值 A 或 B，产生的贡献就是赋的值乘上区间另一种元素的和，于是我们可以维护两个 tag，维护另一个和要乘多少，如果一个区间还没下传标记就已经修改了 A 和 B，那么此时就不能维护到原有的 tag 上了，再维护一个 tag 记录单个节点 A\times B 的值，然后下传的时候乘上区间长度产生贡献，加上时间 tag（需要维护两个，第一次没下传的更新和最后一次更新的时间），还有原本就需要的维护两个，总共七个标记。

教训：ull 不能用memset初始化1，这一堆烂 tag 改了好几天，结果输出写成 lld 了一直在那输出 -，害我白 WA 三发。

话说这个东西怎么抽象成扫描线的啊。

复杂度 O(n\log n)。

Excluded Min

放点有水平的线段树。对答案扫描线的牛逼思想+一个牛逼 trick。

题意是给你一个序列，然后若干次询问，每次询问一个区间，问由这个区间的数组成的可重集合，经过若干次“操作”，能够达到的最大 mex。其中一次“操作”是指，把一个出现次数大于 1 的值 x 变为 x-1 或 x+1。

容易发现判断一个可重集合能否达到一个 mex 的方法是判断在答案的值域内的数是否大于等于答案 -1。mex 这种东西不能二分，然后我第一次在某模拟赛做这个的时候只想到了一个 n\sqrt n\log n 的平庸做法，喜提 40。

大致思路就是用莫队加线段树维护，用线段树维护以某个值为答案能否合法，可以简单用一个式子转换成这个点的值是否大于等于零来判断是否合法，每次区间加入或删除一个数只用在线段树上区间修改，然后在线段树上二分，找到最靠右的值大于等于 0 的位置，查询的复杂度是单 log 的，对于区间互不包含的百分之三十，可以把区间排序后做到 n\log n。

下面说正解，非常逆天。对答案扫描线，从上往下扫答案，判断有哪些区间可以满足当前答案。但是我们发现很难维护这些区间，这时就有一个非常牛逼的 trick。我们发现对于两个互相包含的区间，被包含的区间的答案一定小于等于包含它的区间的答案，于是我们先只提取出来不被包含的区间，等这个区间找到答案再把它包含的区间取出来。

这个想法非常的好，因为如果区间互不包含，那么可以排序使得这些区间的左右端点同时单调。你删除一个位置的元素的时候他就只会影响到一段区间。这时对提取出的区间维护答案就很容易了，每次把枚举到的答案的值对应的每个位置删掉就行了，用线段树维护。

然后考虑如何维护还没被加进去的区间，再用一个线段树维护，我们删除一个区间时，加入被它包含的区间的时候，我们需要注意什么呢？我们需要注意不漏（不会落下区间），并且不与已经取出的区间产生互相包含的关系，至于是否会重复取出就不用担心了，因为一个区间被取出后线段树里也会对应删除它。为了满足上述条件，我们需要维护左端点在某一个区间内，右端点最大的点，然后注意删除一个区间时，可能会取出来很多它包含的区间。

这时还有一个问题，就是新取出的区间的值（我们在第一个线段树里维护的值）是多少，由于它一开始没被取出来，我们需要重新计算这个值，这个也很容易，用另外一个树状数组，维护这个区间还有多少小于答案的点即可。

具体实现细节，比如找到第一个线段树要更新的区间之类的可以再开个 set 来辅助比较好写，最终复杂度是 n\log n。

PermutationForces

做完上面的题以后蔬菜推的。

首先考虑暴力，我一开始考虑的是二分答案，然后发现在答案确定的情况下，删点的顺序不影响结果，删点不会使情况变劣。于是我们发现不需要二分答案，每次选择删除代价最小的点删除即为最优，然后用当前的最小代价更新答案，证明很容易，简单想一下就好。

然后我们考虑如何找到当前代价最小的点，暴力是 n^2 的，显然不能接受。

我们发现每次删除一个点我们假设是 (i,p_i)，那么它会对哪些点产生影响呢？它会使 (j(j<i),p_j(p_j>p_i)) 和 (j(j>i),p_j(p_j<p_i)) 的点产生影响，使它们的答案 -1。这个也是容易想到的，但这是一个二维关系，很难维护，我想了想感觉树套树也不行。

蔬菜提醒我和上一个题联系起来。

虽然是一个二维关系，但是实际点的个数只有 n 个，于是我们用区间的角度去考虑每个点 (i,p_i)。

题解好像写的比较简单，我懒得看了，我这里就说一下我的巨屎分讨写法吧。

我把 p_i>i 和 p_i<i 分成了两类，然后我们把 p_i 和 i 当成一个区间的两端，这时我们发现对于每类区间，被包含的区间一定能比包含它的区间先被删除，这个证明我也懒得解释，不太会说，很容易想出来。

于是又变成了上一题的情况，只不过刚好相反，这次维护的是被包含的区间，然后由于我们分了两类，需要用四棵线段树来维护答案和没被提取出来的点，然后用上面说的更新已经被提取出来的点，这个时候你发现有一个很好的地方，就是你实际删除一个点只会更新另一类区间的某一段的答案，不用再分讨一大坨了。

这时我又卡住了。我不会计算新提取出来的区间的答案了，我被禁锢在了用上面的方法来更新答案的形式了。后来想了想，发现和上一题一样，新提取出来的区间可以直接换一个角度计算答案，我们只需用两个树状数组记录被删除的点的 i 和 p_i，然后提取出新的区间时计算答案，就算一下有多少 p_j<p_i 的被删除的点以及多少 j<i 的被删除的点就好了。

写了 5.3k，单 log 的做法跑了两秒，常数巨大。

[博弈论]()

外培的时候做的原创题，不挂链接了。蔬菜又场切了。

题意给一个 10^5\times 10^5 的 01 矩阵，初始全是 0，每次给一个矩阵区间翻转，询问有多少个子矩阵满足最左测一列全是 1 或最右侧一列全是 1。

首先需要想到扫描线。这里说从上往下扫的思路，（从左往右也可以扫）。然后考虑如何统计贡献，假设到当前这一行第 i 个节点往上连续的 1 的长度是 a_i，那么就有一个非常巧妙的转化，就是把这个 a_i 从小到大排序后统计答案为 \sum a_i\times rk_i。

然后考虑怎么维护这个东西，我们发现我们需要维护的操作只有区间翻转，而区间翻转后，原来是 a_i>0 的会全变成 0，而原来是 0 的只会变成 1。我们发现这实质上是一个区间摊平的操作，于是可以用珂朵莉树维护。这里要注意：一个区间翻转不是把它们全部摊平成相同的值，而是会摊平成两种值，我们不是要维护每一个连续的 0 段或 >0 的段，而是维护每一个区间翻转的整体，可以理解为维护一个时间戳。

我们发现随着扫描线往下扫，没被翻转到的区间，原来非 0 的部分 a_i 会自然的长 1，而原来是 0 而且还不被翻转的是不会长 1 的，因此 a_i 为 0 的要和不为 0 的区分开，至于如何维护这个自然增长的长度，我们可以维护它们的行数，然后用当前行数相减即为真实答案。

由于每一个时间戳上的 a_i 的值只可能有两种，0 或者一个大于 0 的值，所以每次维护一个珂朵莉树上的区间翻转相当于在我们维护的数据结构里加入若干个 1，以及删除若干个 a_i，所以我们需要统计这个区间里有多少非 0 的值，这个可以用一个线段树来维护，维护区间翻转操作即可。

然后考虑维护贡献的数据结构，答案会发生什么变化，每次从中删除若干个值为 a_i 的元素，把它们变为 0 ，对于 a_j>a_i 的部分答案是没有影响的，因为它们的排名没有变，对于 0<a_j<a_i 的部分，它们的排名都增加了若干，于是增加的贡献就是 \displaystyle\sum_{a_j<a_i} a_j，用一个树状数组维护即可，然后由于我们前面说了要用行数差来维护这个值，所以还得再用一个树状数组维护个数。

然后注意每次多扫一行，更新整体增加的答案（没被翻转的地方也会增加答案）。总计，需要两个树状数组，一个珂朵莉树，一个线段树，复杂度单 log。

主席树

翻到了之前做过的题，发现做过的都忘了。

神秘数（突然想起来以前还在这题里跟人对线过，不过要不是看到那个帖子也不会发现这么好的题）

考虑暴力。对于一段区间 [l,r]，升序排序后，枚举，若当前能够表示的区间是 [1,x]，如果 a[i]<=x，就直接更新区间到 [1,x+a[i]]，否则 x+1，永远无法表示，直接输出即可。

怎么优化。假设当前的答案是 ans，在这个区间中再找值小于等于 ans 的数字之和，如果小于 ans，就直接输出。否则就把 ans 变为找出来的和加一，这样可以保证 ans 至少是倍增的，而找值可以用主席树维护。

Rollbacks

我们需要快速地切换版本和更新版本，于是用主席树维护。

但是这个题维护版本也挺麻烦的，因为既有添加又有删除。但有一个突破口，就是撤回操作不可撤回。也就是说一旦发生撤回操作，它撤回之的这一步以后再也不用管了。

于是考虑维护相对位置，我们发现不管你对后续做什么操作，当你撤回到某一个操作的时候，这个序列都是一定的。它前面的第几个是谁就是谁，其实就是个树，它的祖先不会变，但是兄弟和子孙会变。

因此考虑倍增维护祖先。

然后 MLE，空间占用 320M。为啥要限制到 250M 啊。

翻题解。发现有高妙做法。把主席树底层 30 个位置一压，好像是叫底层分块。然后我发现还过不了，270M。。

于是求助蔬菜，然后它提供了一种更聪明的做法。可以用 vector 替代掉倍增数组，再套上我 180M 的底层分块主席树，刚刚好。

这题其实有优雅 O(q) 做法。

浅谈势能分析

今天看了 splay 的势能分析。看了很久还在群友的帮助下才理解。没有深刻掌握，这里只是简单的记录一下我的理解。

对于一些不好直接分析复杂度的做法，采用放缩的形式，把若干次操作放缩成势能的变化，就是设计一个势能函数，使得能够把每次操作放缩成相邻两个状态的势能差，然后就能使多次操作放缩成始末状态的势能差。

例如 splay 的势能分析，它甚至为了构造成两个状态的势能差，还把复杂度凭空又加了一个势能值，用加上势能值的上界减去势能本身的下界得到真正的上界，很神奇。

真的不知道人类是如何想出来的。