浅谈 OI 中的数据结构题

## -1 一些奇怪的东西 事情的起因是这样的： 某天晚读。 DPair： 我不想晚读了，要不我们讲课吧。 其他人： 那你来讲分块。 DPair： 算了算了我们还是晚读吧。 DPair： 你们不会真的要我讲分块吧。 然后。  然后。 DPair： 我要杂题选讲。 devinwang： 不行，最好要有个主题。 于是就有了这篇博客。 ## 0 前言 这篇博客将会整理目前我自己觉得比较有用的一些数据结构的技巧，与杂题选讲相互配合。 为了满足所有选手的需求，前半段的博客会极其简单，后半段会比较基础，有实力的选手可以跳过自己不需要的内容。 **注：离线算法 xtr 讲过了，所以我不讲了（（** ## 1 分块的常用技巧 分块是一种~~时代的眼泪~~非常适合骗分的算法，虽然现在一般不在~~除Ynoi外的~~题目中作为标算出现，但是其作为部分分以及艹标算的骗分工具还是十分有效的。 下面简单介绍几种分块的常用技巧 顺便宣传一下一个[分块入门题单](https://www.luogu.com.cn/training/62596) 。 ### 1.1 前置知识 - 循环结构 - 数组 - 模拟 - 一定的数据结构基础（当然没有关系也不是很大） ~~没错这些都会你就能学分块了~~ ### 1.2 值域分块 值域分块，顾名思义就是在值域上分块，似乎一般用来均摊复杂度，比如有些时候会以 $O(\sqrt{n})$ 修改 $O(1)$ 查询代替两者均为 $O(\log n)$ 的权值树状数组。 #### 1.2.1 适用范围 一般当我们发现一道题是分块题且有些操作和值域有关，或在复杂度带 $\sqrt{n}$ 的题中发现需要使用带 $\log$ 的处理值域的数据结构时，就可以考虑值域分块。 具体分块的方法和序列分块相差并不多，下面以一道例题作为讲解。 #### 1.2.2 例题讲解 #### 例2：[P4396 [AHOI2013]作业](https://www.luogu.com.cn/problem/P4396) **题意简述** 给定了一个长度为 $n$ 的数列和若干个询问，首先你要统计区间 $[l,r]$ 内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在区间 $[l,r]$ 中出现过的 **数值** 的个数。 **分析** 做法：莫队+值域分块 首先显然第二个询问就是第一个询问去重后的结果，这个在莫队的时候直接去重即可，故下面我们只讨论第一个询问。 首先我们有一种比较劣的做法，就是莫队的时候用 $O(\log n)$ 的权值线段树进行修改，然后在处理完区间后进行一次在值域上的区间查询（这是由于每一次查询的 $[a,b]$ 区间各不相同），可以使用类似这样的实现： ```cpp for (int i = 1;i <= m;i ++){//遍历排完序的询问 while()... while()... while()... while()...//莫队的区间左右端点移动，这里不多赘述 ans[id]=query(a,b);//在值域上区间查询，而不是实时维护 } ``` 这样子复杂度是 $O(n\sqrt{n} \log n)$ 的，并不能通过本题。 但是我们不难发现，我们修改进行了 $O(n\sqrt{n})$ 次，但询问只进行了 $O(n)$ 次，这里并不均匀。 所以我们使用值域分块均摊复杂度。 我们先想一想有什么可以 $O(1)$ 修改，没错就是一个数组。 然后我们会发现在数组上的修改虽然是 $O(1)$ 的，但查询是 $O(n)$ 的。 不过我们又惊喜的发现，这是一个 “单点修改，区间查询” 的数据结构，所以可以采用类似序列分块的手法。 首先考虑修改，我们仍然需要 $O(1)$ 修改，但又要方便后面的查询，故我们还是对于每一个 **值域上的块** 维护一个 $sum$ 表示区间和，那么每一次单点修改就只修改 **对应的值** 以及 **对应值所属的块** 的信息即可。 那么查询就类似序列分块了，可以 $O(\sqrt{n})$ 实现。 那么莫队的部分就变成了 $O(n\sqrt{n})$ ，而查询的部分虽然看似退化成了 $O(n\sqrt{n})$，但是我们均摊整体复杂度为 $O(n\sqrt{n})$ 了，于是复杂度正确，并可以通过本题。 #### 1.2.3 算法优劣 优势： 可以有效处理值域上的问题并与各类根号算法均摊复杂度以达到全局复杂度正确。 劣势： 复杂度带 $\sqrt{n}$ 而不是 $\log$ ，相对较慢，无法处理 $10^6$ 级别的数据。 （不过这个劣势由于值域分块的适用范围基本可以忽略不计） ### 1.3 根号分治 严格来说这应该不是分块 #### 1.3.1 适用范围 但是这个东西还是比较有用的，经常能配合分块或者莫队等处理一些奇奇怪怪的问题。 似乎一般拿来处理的问题都和除法或多或少有一些关系。 #### 1.3.2 算法流程 首先对于这种题目，我们考虑设置一个阈值 $limit$ 。 对于 $> limit$ 的数据，会有一些性质，我们根据这个性质进行处理。 对于 $\le limit$ 的数据同样也会有一些性质，我们也根据这个性质特殊处理。 而且这两部分若缺少了这些性质复杂度就难以保证，但把它分开了复杂度就对了。 我们 $limit$ 一般取 $\sqrt{n}$ ，但实际情况实际考虑。 #### 1.3.3 特殊性质 根号分治在某一些题目里会存在一些优美的特殊性质，这一些性质对解题会有很大帮助，下面简单说几种我见过的常见性质。 我们先考虑 $\le limit$ 的那一部分。 1. 若考虑对值域根号分治，这一部分数最多有 $limit$ **种** 这个性质可以用于对于每一 **种** $\le limit$ 的数进行 $O(n)$ 的预处理，然后就可以使得后面的一些操作忽略这一部分。 一般是 $> limit$ 的部分可以在值域上暴力的时候会把这一部分分离出来处理，另一部分的处理见后文、 2. 若考虑对值域根号分治，这一部分数值最大为 $limit$ 这是显然的吧。。。但仍然有一些作用。 比如说我们有些题目可能要存形如 $a[i \in[1,V]][j \in[0,i-1]]$ （其中 $V$ 为值域）的信息。那么我们就可以暴力存 $i \le limit$ 的信息，另一部分后面再考虑。 然后再考虑 $> limit$ 的那一部分。 1. 若考虑对出现次数根号分治，则这一类数最多有 $n \over limit$ 个 这是显然的，但是在 [P5397 [Ynoi2018] 天降之物](https://www.luogu.com.cn/problem/P5397) 的根号分治做法中有很重要的意义。 2. 若考虑对值域根号分治，则这一类数在值域中的倍数最多有 $V \over limit$ 个。 于是我们做一些和 “取模” “倍数” 有关的题目时，这一部分暴力的复杂度是对的。 这个没什么例题好讲的。 ## 2 珂朵莉树的应用 珂朵莉树是一种著名的暴力，在数据随机的区间推平题目当中有相当不错的效果。但是，珂朵莉树在 OI 中的运用远不止这点暴力，它可以非常方便的维护一些和 **连续段** 能扯上关系的问题。 ### 2.1 具体应用 虽然珂朵莉树的实现十分暴力，但是有些时候，在我们对复杂度一番分析之后，会惊奇的发现用珂朵莉树维护一些东西不仅复杂度正确而且十分方便。 下面举一些例子： #### 例1：[P2824 [HEOI2016/TJOI2016]排序](https://www.luogu.com.cn/problem/P2824) **简要题意** 给你一个排列，要求支持区间升序或降序排序，**最后** 单点询问。 **题解** 这是一道非常经典的珂朵莉树思想的运用。 什么？你跟我说二分答案？ 那要是这道题要求随时查询，而且甚至可能出现区间和这一类区间查询呢？ 那就不好做了，所以我们还是考虑一种通法。 首先我们可以把一个 **有序段** 作为一个连续段处理，每一个连续段用一棵权值线段树来维护。 具体来说原来珂朵莉树存储的 `l, r, val` ，在这里应该改为 `l, r, rt, tag` ，分别表示区间 $[l, r]$ ，以及对应的动态开点权值线段树上的根编号还有升序或降序。 然后我们就可以利用珂朵莉树的思想进行区间排序了，不难发现和区间推平十分类似，也是把一堆连续段变成一个大连续段。 只不过我们一开始可以直接删除一段区间然后丢一段新的进去，现在我们需要先把被删除的那一堆连续段线段树合并，然后再丢进去。 对于区间的分裂，考虑采用线段树分裂，复杂度还是对的。 那么这样珂朵莉树的部分就转化成了一个只有推平的珂朵莉树，复杂度单次 $O(\log n)$，然后线段树 **合并 + 分裂** 的总体复杂度也是 $O(n\log n)$ 。 而且这两部分是加起来的， $n, m$ 又同阶，所以总体复杂度甚至达到了 $O(n\log n)$ 。 ~~比什么二分答案不知道高到哪里去了~~ ## 3 杂题选讲 这篇博客还是纯粹一点比较好，杂题选讲换个场地。 **有近一半不是分块题** 前两道题是开胃菜，做过的同学不要声张。 后面的题目除了 5 7 8 以外，都与前面的知识点或多或少有些关联，所以说相互配合 [链接](https://www.luogu.com.cn/blog/DPair2005/shuo-ju-jie-gou-za-ti-jing-xuan)