ODT的映射思想的推广

首先，我们先介绍推广的必要条件：即在推广到不带有区间覆盖的情况下，必须牺牲复杂度,但是能保留珂朵莉树的优秀常数。 众所周知，一般的题目我们会用块状链表来写。但是这玩意拆来拆去并来并去常数会很大。因此，我们希望有一个结构代替块状链表。 众所周知，链表维护的珂朵莉树不用拆来拆去，只需要快速的 `split`，而且在一开始的阶段块数较少，有较小的常数。众所周知，替罪羊树只需要定期维护一次，维护之后就能保证性质的优美。 于是，我们自然而然地有了想法：缝合。 我们发现，珂朵莉树有一个弊端: 必须有区间覆盖。 如果没有区间覆盖操作，珂朵莉树的复杂度将会水涨船高——这时候我们就要用到替罪羊树的方法:满了，就炸掉重构。 于是我们就得到了能够保证根号复杂度的珂朵莉树。 ## 扩展后的ODT:映射、状态压缩 先看看珂朵莉的原题，在这题中珂朵莉树上的节点维护了这么几个信息：区间左端点，区间右端点，区间颜色。 这就是珂朵莉树的状态压缩思想，只要我们知道这三个值，我们就可以推算出这个区间里有哪些数。 因此，我们可以把这个思想推而广之。 ### 类ODT链表 我们不妨把如下的数据结构称为类ODT链表： 在链表上，每个节点代表一段序列，但是只维护少数变量。如珂朵莉树中，用 $l,r,x$ 表示原序列从 $l$ 到 $r$ 都是 $x$ 关于类ODT链表的维护，对于散块可以通过 `split` 操作来实现，而整块直接打标记即可。 ### 单纯的状态压缩 [P3391 文艺平衡树](https://www.luogu.com.cn/problem/P3391) 题目要求我们每次将某个区间翻转。 我们可以把它与珂朵莉树进行类比： 在珂朵莉树中，每个节点代表的块是同一种颜色 而在这题中，原序列是有序的，那么我们可以维护一个类ODT链表，链表中，每个节点代表的块是一个公差为 $1$ 或者 $-1$ 的等差数列，我们用 $l,r,rev$ 来表示这样一段序列。 一开始的珂朵莉树里自然只有一个节点，即完整的一段序列。 然后，当我们维护的时候，如果要翻转某个区间，我们就把这个区间的端点所在块找到，然后对两个端点所在块进行珂朵莉树的核心操作：```split``` 。 接下去，只要把两个端点中间的那些块暴力翻转并且打标记即可。 考虑到这样会导致块数暴增，我们需要寻找新的性质。 这题每次的操作都是置换群上的一个置换。因此我们只需要维护置换即可。 因此我们可以进行重构：即，当块数大于 $T$ 时，计算出当前序列，然后新建一个 $1$ 到 $N$ 的常置换存到类ODT链表中，再进行计算。复杂度是 $O(MT+N\frac M T)=M\sqrt N$ 的，实际算上常数比很多Splay优秀。 这是本题用类珂树结构的写法题解 :[文艺平衡树 分块题解](https://www.luogu.com.cn/blog/101734/p3391-ti-xie) 这是类ODT写的最优解榜一代码：[文艺平衡树 最优解](https://www.luogu.com.cn/record/87883658)（202ms，比最快的splay快了30ms，比极限卡常的vector快了20ms） ### 节点到区间的映射 我们考虑的这样一个题。 区间求和，单点插入，区间加。 对于这个题，乍一看好像没法进行状态压缩，因为我们没法找到一个区间的共性。那么我们就可以使用第二个方法：映射。 我们先维护一个序列 $a$，表示初始序列。 然后我们的节点可以写成 $l,r$ ，表示序列 $a$ 从 $l$ 到 $r$ 的这段。另外，我们再对序列 $a$ 做一个前缀和。 做区间加的时候，我们只需要维护一个暴力的 `split` 然后依次打标记。 做单点插入的时候，`split` 完插入的时候可以加个标记来表明这是一个单点，也可以直接插到序列 $a$ 的末尾 仍然是通过定期重构来维护。 由上，我们得到了类ODT结构的另一个用法：直接映射到原数组。可以选择使用指针式写法或者映射式写法。 如图所示，每个节点代表原数组上的其中一段。  ### 总结 经过以上两点，我们大概得出了一个结论。 推广ODT的实现需要满足这样的条件: 可以迅速地用少量的变量就能代表一个区间，从而实现快速的 `split` 。 在一般的情况下，最终的复杂度为：$O(Query\times T\times M+ Init\times \frac M T)=O(M \sqrt{Query\times Init})$ 其中 $T$ 为重构次数，$Query$ 为每块查询复杂度，$Init$ 为重构复杂度 ## 进阶指南 这种扩展ODT除了维护普通块状链表可以维护的内容以外，还可以维护一切满足以下三个性质的题目： 1. 满足相对稳定性。即两个点间的距离保持相对稳定。（若仅有单点交换的话，可以当成单点删除和单点插入来做，仍然保持相对稳定） 2. 在静态的时候，可以迅速维护某个区间与某个数组叠加后的答案。例如：静态区间众数、权值分块。 3. 预处理必须快。如果是根号的预处理那么会寄。 或者，也可以不满足相对稳定性，但是满足区间查询具有优秀复杂度，同时要能有区间累加性。所以它不能维护带区间翻转的区间第k小值也就成为了它相对块状链表的弊端之一了。 但是相对的，它可以维护很多其他数据结构较难维护的内容：带插区间众数。 我们可以将类似的题目都成为蒲公英式分块。 ### 带插区间k小值 [带插区间k小值题面](https://www.luogu.com.cn/problem/P4278) 可以看我下面的题解。这题在静态的情况下是把散块按到整块里来实现的。而大多带有“把散块按到整块里”的思想的分块都能用这个东西动态化。 但是要注意复杂度是 $O(N^{\frac 2 3}M)$，不如一般块状链表。 [带插区间k小值题解](https://www.luogu.com.cn/blog/jinkel/solution-p4278) ### 带插区间众数 目前来讲这个东西貌似还只有斐波那契堆和类ODT链表两个做法？ 斐波那契堆那玩意太反人类了，我们介绍下萌萌的 ODT 吧。 同样的，我们维护一个映射。在原数组上我们维护好静态的区间众数所要维护的两个数组。 然后我们就可以迅速找到查询数组在原数组上对应的区间，然后我们只需要把插入的点当成散块就可以做了。可以参考[P4168 蒲公英](https://www.luogu.com.cn/problem/P4168)来维护静态内容。 重构是 $O((\frac N T)^2+(\frac N T)N)$ 的,单次查询则是 $O((T_2+T))$ 所以总复杂度是 $O(\frac {N^2} T\times \frac M {T_2}+M(T_2+T))$ 的，取 $T_2=T=N^{\frac 2 3}$ ，总复杂度是 $O(N^{\frac 2 3}M)$，与斐波那契堆做法复杂度相同。 ### 其他 带插入区间逆序对的复杂度较高，而且由于静态时候要做到 $O(N^\frac32)$ 的复杂度是因为借助了左右散块有顺序的特点而进行的归并排序，而散点并没有类似性质，从而导致复杂度会多出来一个 $log N$，并没有太大实现意义。 而带插入的区间袜子配对、区间偶数出现次数数个数等都是与区间众数等价的，但是用斐波那契堆并不能很好地维护，此时用类ODT是比较有效的方法。 ## 优劣分析 事实上它可以代替大部分情况下的块状链表和Splay，在复杂度相同的情况下常数较低，但是经常出现复杂度较高的情况。类ODT链表通常比较暴力且容易想到，应当酌情选择。 在区间众数之类分块之后不能用前缀和之类思想维护的东西就只能用类ODT链表了。和斐波那契堆有一样的复杂度，但是常数明显的更小。 类ODT链表是一种维护区间映射的思想，因此通常没有固定形态。它的使用也需要因题而变迁。