数据结构总结
MoonCake2011
·
·
算法·理论
数据结构总结为假，分块总结为真。
让我们把这个世界分块吧！
算术天才⑨与等差数列。
首先，有个性质是如果 a 为等差数列打乱，那么 \gcd(a_2-a_1,a_3-a_2,\dots)=k，k 为公差。
然后尝试用线段树维护 Hash。
然后设 x 的 Hash 权值为 \text{Base}^x \bmod \text{Mod}，然后判断等差数列的时候就可以用等比数列求和公式乱推一下就能做了。
[Ynoi2013] 对数据结构的爱。
考虑在线段树节点上维护分段函数 f，f(x) 表示 x 进入这个区间后出来时是减了多少乘 p，显然，这是一个满足单调性的分段函数，且最多有 r-l+1 个段。
得出合并式子。
暴力合并过不了。
$f_{\text{lson,x+1}}\le f_{\text{rson},y}-s_{\text{lson}}+x\times p$ 时，我们就可以直接去 $x+1,y-1$ 枚举了。
这样跳，$y$ 最多减少 $n$ 次，所以合并 $O(r-l+1)$ 的。
查询是就可以直接二分了。
所以时间复杂度是 $O(n\log n+m\log^2 n)$。
[[Ynoi2000] rspcn](https://www.luogu.com.cn/problem/P9995)。
首先，可以尝试使用 `set` 维护每个有序段。
排序就直接暴力裂段然后暴力扫就行了，这样可以证明时间复杂度 $O(n\log n)$。
每个有序段可以用权值线段树维护，然后分裂和合并就行了。
可以在线段树上维护每个权值是否在序列里第一次出现，有就 $+1$，次过程用树状数组维护即可。
[[省选联考 2020 A/B 卷] 冰火战士](https://www.luogu.com.cn/problem/P6619)。
一个方案耗费能量是冰能量之和与火能量之和的最小值。
对于一个温度，冰的能量递增，火递减，设一个温度 $T$，火方的能量和是 $f(T)$，冰方能量和是 $g(T)$。
我们把最小值拆开，分类讨论，于是我们现在需要第一个温度 $T$ 使得 $f(T)\le g(T)$。
这可以用树状数组维护然后树状数组倍增求得，剩下我们直接取求得的 $T$ 两边的答案就行，这非常好求。
于是我们有了一个 $O(n\log n)$ 的算法。
[[PA 2017] 抄作业](https://www.luogu.com.cn/problem/P11807)。
可持久化线段树模板，可以在可持久化线段树上维护 Hash。
这样可以在可持久化线段树上二分来比较两个数组来 sort，时间复杂度 $O(n\log^2n)$。
[[TOIP 2023] 公路](https://www.luogu.com.cn/problem/P11852)。
自己做出来的一道紫题。
把这一道纯数据结构题来做，你就无敌了。
但是我确实把这道题当成一道纯数据结构题做了，没用边双连通分量。
首先，看到这题会想着在最小生成树上进行一些操作，于是先将最小生成树建出。
接着尝试考虑所有非树边，可以将一条非树边看作一条路径 $(a,b)$。
设覆盖一条边 $(u,v)$ 的最小的非树边的权值为 $t(u,v)$。
发现对于一条路径 $(u,v)$，答案为路径上所有边的 $t(u,v)$ 的最大值，这个其实手模一下很好证明。
然后就直接暴力乱用 `multiset` 与启发式合并再搞个倍增就完了。
注意卡常。
[小B的询问](https://www.luogu.com.cn/problem/P2709)。
尝试用莫队。（设 $n,m$ 同阶）
这个问题有一个朴素的做法就是每次暴力移动左端点和右端点，然后只用考虑加数和删数的问题了（每次加删数是 $O(1)$ 的）
但这样可以被卡到 $O(n^2)$，考虑优化。
首先，对序列分成 $B$ 块，然后对询问分为 $\dfrac{n}{B}$ 组，第 $i$ 组的左端点在第 $i$ 块内。
对于每组的询问，按询问右端点排序。
这样，对于每组的右端点最多移动 $O(n)$ 次，每次的左端点一次最多移动 $O(\dfrac{n}{B})$ 次。
所以总复杂度是 $O(nB+\dfrac{n^2}{B})$，可以取 $B=\sqrt{n}$ 来达到复杂度最小值 $O(n\sqrt{n})$。
实现对询问分组的时候可以不那么复杂，不用把组显式的分出来，可以写成下面这样。
```cpp
struct node{
int l,r,id,ans;
}q[1000010];
inline int get(int x){
return x/len;
}
inline bool cmp(node x,node y){
if(get(x.l)!=get(y.l)) return x.l<y.l;
return x.r<y.r;
}
```
莫队有个常数优化，就是对于编号为奇数的块 $r$ 升序排序，偶数就降序。
```cpp
inline bool cmp(node x,node y){
if(get(x.l)!=get(y.l)) return x.l<y.l;
if(get(x.l)&1) return x.r<y.r;
else return x.r>y.r;
}
```
原理是可以让 $r$ 指针不用每次跨块的时候从比较大的位置回到比较小的位置而是降序处理询问。
莫队的常数很小，正赛中 $5\times 10^5$ 没有问题，$10^6$ 勉强跑跑。
代码又短又好写。
[[AHOI2013] 作业](https://www.luogu.com.cn/problem/P4396)。
看到静态问题，考虑莫队。
但是现在需要询问值域 $[a,b]$ 里的东西了，我们怎么办呢。
尝试在莫队里用树状数组统计，每次询问直接 $O(\log n$ 查询即可，但这样 $O(n\sqrt{n}\log n)$ 显然过不了。
我们需要用上和树状数组一样简短的值域分块，直接对值域分块（有时需要离散化）。
对每个块统计相应的答案，散块暴力（就相当于分块区间查询）。
然后这样插入 $O(1)$，询问 $O(\sqrt{n})$，时间复杂度 $O(n\sqrt{n})$。
代码又短又好写。
[参数要吉祥](https://www.luogu.com.cn/problem/P12598)。
可以直接莫队 + 值域分块统计。
每次加数删数时可以用桶直接统计，每次统计答案时可以在值域上分块获得一个 $O(n\sqrt{n})$ 的算法，也是个经典做法。
代码又短又好写。
[Rmq Problem / mex](https://www.luogu.com.cn/problem/P4137)。
QMR Problem（不是
可以直接莫队 + 值域分块统计。
代码又短又好写。
[[Ynoi Easy Round 2016] 掉进兔子洞](https://www.luogu.com.cn/problem/P4688)。
上面两道是给你们投经验的，这道才是重头戏。
答案可以推出是三个区间长度减去三个区间共有的数的个数。
你会发现这很难做，因为每次询问是三个区间（~~要不直接 6 维莫队 $O(n^{\frac{5}{6}})$ 吧~~
你发现了时限是三秒，于是你想到了 `bitset`，尝试 $O(\dfrac{n^2}{w})$。
然后你发现你统计的不是公共的颜色数，而是数的个数。
于是可以用一种神奇的离散化。
设这个序列里出现了 $k$ 个 $x$，于是 bitset 里 $[pos,pos+k-1]$ 的都用来统计 $x$ 这个数。
假设 $x$ 在区间里出现了 $t$ 次，那么它会占满 $[pos,pos+t-1]$。
对于每次询问，我们就只用求三个区间对应的 `bitset` 然后把它们 `&` 起来用 `.count()` 函数求 $1$ 的个数就行了。
直接将 $m$ 个询问拆成 $3m$ 个询问跑莫队，用 $m$ 个 `bitset` 记录答案，莫队统计答案的时候 `&` 一下就行了。
但是 $10^5\times 10^5$ 的 `bitset` 开不下，于是我们可以将原来的 $m$ 组询问拆成三组，每组询问跑莫队统计就行了。
[[Ynoi2019 模拟赛] Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048)。
显然 $O(n\sqrt{n})$ 做法，尝试序列分块。
首先，我们可以记录两个块之间所有块的区间众数出现次数。
我们将每个数出现的位置存进一个 `vector` 里，并记录每个位置在 `vector` 里对应的位置。
然后你会发现剩下的散块最多让答案 $+2\sqrt{n}$。
于是我们可以像 Hash 解模板 manacher 一样暴力扩展即可，于是你会 $O(n\sqrt{n})$ 的区间众数了。
[[Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446)。
考虑分块，设块长为 $B$。
设 $P_i$ 为 $i$ 一直跳父亲知道跳出块外的跳到的节点编号。
$2$ 操作很显然很好做。
考虑 $1$ 操作怎么维护，因为我们发现对于一个块的 $P_i$ 只能暴力维护。
但是我们发现一个块被 $1$ 操作**有效**整体操作 $B$ 次所有节点就会一次跳出块外。
于是对于整体 $B$ 次以内的块就暴力遍历块内所有数依次更新（可以递推的），$B$ 次外的就直接 $P_i=fa_i$。
然后时间复杂度 $O(nB+\dfrac{n^2}{B})$，取 $B=\sqrt{n}$ 最优时间复杂度为 $O(n\sqrt{n})$。
[[省选联考 2025] 追忆](https://www.luogu.com.cn/problem/P11831)。
首先，有向无环图可达性问题是只能做到 $O(\dfrac{n^2}{w})$ 的。
考虑 $O(\dfrac{n^2}{w})$ 的做法，于是尝试使用操作分块，设每 $B$ 次询问重构一次。
最开始肯定是要预处理可达性的。
对于每一个操作块，可以先忽略那 $O(B)$ 个修改的点，等每次询问暴力 $O(B)$ 枚举一下。
剩下的点我们对 $a$ 的值域进行分块并记录每个 $a$ 只对应的编号，设块长为 $L$，每个询问块对每一值域块跑一遍拓扑排序求对于每个点 $b$ 的最大值。
每次询问可以散块暴力判断，整块直接取 `max` 就行了。
设 $n$，$q$ 同阶，时间复杂度 $O(\dfrac{n^2}{w}+nB+\dfrac{n^3}{BL}+nL)$，可以得出最优块长为 $B=\dfrac{n}{w},L=\sqrt{nw}$，此时时间复杂度 $O(\dfrac{n^2}{w}+n\sqrt{nw})$，注意卡常。
[[SHOI2006] 作业 Homework](https://www.luogu.com.cn/problem/P9809)。
吃了那么多的粪，来个好的。（根号分治模板题）
这题有两种朴素的做法（设 $n$ 和值域同阶）。
第一种是对于每个询问暴力遍历 $\dfrac{n}{Y}$ 次，插入操作插入一个数，每次查询集合里大于等于某个数的最小数，我们使用值域分块记录一个数在块内的后继，和一个块往右的最小数，然后就可以 $O(\sqrt{n})$ 修改，$O(1)$ 查询（可以证明取块长为 $O(\sqrt{n})$ 最优），这样时间复杂度是 $O(n^2)$ 的。
第二种是对于每个修改记录 $X$ 对每个 $Y$ 的答案，这样是 $O(n^2)$ 的。
尝试拼接两种暴力（怎么和操作分块长得那么像呢），设定一个阈值 $B$。
对于 $<B$ 的 $Y$，选择用做法二记录，时间复杂度 $O(nB+n\sqrt{n})$。
对于 $\ge B$ 的 $Y$，选择用做法一，时间复杂度 $O(\dfrac{n^2}{B})$。
解得 $B=\sqrt{n}$ 时最优，时间复杂度 $O(n\sqrt{n})$。
[[Ynoi2011] 初始化](https://www.luogu.com.cn/problem/P5309)。
其实和上题差不多，尝试根号分治。
设阈值 $B$，对于 $<B$ 的数，直接暴力修改，需要序列分块修改。
对于 $\ge B$ 的数，发现直接记录修改复杂度很低，查询复杂度会很高，于是可以对于每个模数 $p$ 的统计数组，记录前缀和和后缀和来平衡复杂度（此时修改就需要暴力了）。
查询时对于 $<B$ 的数，直接分块查询，$\ge B$ 的数，可以用前缀和和后缀和查询。
[Count on a tree II/【模板】树分块](https://www.luogu.com.cn/problem/P6177)。
在树上随机撒 $B$ 个点，相邻两点间的期望距离是 $O(\dfrac{n}{B})$。
然后记录每两点之间的桶，这样时间复杂度 $O(nB^2)$，对于一组询问，我们要判断两点间是否有 $\ge 2$ 个特殊点，是否在一个点到 LCA 的路径上没有特殊点，两边都有特殊点的情况。（非常答辩就对了）
对于两点间有 $\ge 2$ 个特殊点的情况，可以直接把散块的答案统计到那两个特殊点所对应的桶里，然后恢复回去就行。
然后每次询问求出每个点上面的第一个特殊点，剩下就直接暴力跳就行了，细节不多，但是需要分讨所以代码很长。（其实很多都可以照抄）
放个[题](https://www.luogu.com.cn/problem/P5356)作为分块大卡常的练习题。