浅谈珂朵莉树

~~又是一个不想写题的下午，所以来整点活.jpg~~ 什么，你问我为什么现在突然想起来要写这个东西？ 你猜 ## -1 前置知识 - `std :: set` 的基础使用（当然不知道也没什么太大关系） - 一定的对于时间复杂度的理解 - 一定的左闭右开思想 - ~~末日三问的番（（~~ ## 0 珂朵莉树 ### 0-0 简介 没错标题是骗你进来的，珂朵莉树我们就简单提一提。 珂朵莉树（又称 “老司机树” 即 ODT ）可以用来处理一些区间推平或类似的问题。 具体来说，我们不难发现一个序列可以用 **某种方式** 被分为多个 **连续段** （甚至是 $n$ 个），然后我们用 `std :: set` 来维护 **连续段**，然后用 `std :: set` 的一些方便的操作来实现一些暴力。 然后经过一些奇怪的推导会发现对于某一些题目来说，用暴力的复杂度是对的。 这就是珂朵莉树的意义所在。 下面我们来讲一讲珂朵莉树的实现： 具体来说我们需要 **一个结构体，两个函数（事实上是一个）**。 ### 0-1 结构体定义 个人喜欢以 `NODE` 为结构体名称 一般的珂朵莉树需要这样子的结构体： ```cpp struct NODE{ int l, r, val; NODE(int l, int r, int val) : l(l), r(r), val(val){} inline bool operator < (const NODE &tmp) const{return l < tmp.l;} }; set <NODE> ODT; ``` 我们已经说过，珂朵莉树是一种用来维护 **连续段** 的数据结构，所以我们需要 $[l, r]$ 来表示一个连续段，一个连续段当中显然有一些东西是我们可以只用一个数表示的，所以再加上一个权值 `val` 。 由于要放到 `std :: set` 里面我们再加一个重载运算符。 ### 0-2 函数实现 珂朵莉树的核心函数个人认为是这个 `split()` 即分裂函数，它可以把一个连续段分成两个。 其意义在于，当我们要对 $[l, r]$ 进行操作时，两边的连续段不一定完整，此时我们就把两边的连续段给分裂出来就变完整了。 比如 $[1, 3], [4, 6]$ 是两个连续段，我们要操作 $[2, 5]$ ，我们就先分裂出来 $[1, 1], [2, 3], [4, 5], [6, 6]$ ，然后就可以只对完整的连续段进行操作了。 可以顺便返回一下分裂出来的连续段的迭代器。 它是这么实现的：（`emplace` 和 `insert` 基本相同，可以直接视为 `insert`） //update：而且用 `emplace()` 似乎不用构造函数，不过似乎要 C++11 以上？（感谢 @_Wallace_） ```cpp inline IT split(int x){ IT it = t.lower_bound(NODE(x, 0, 0)); if(it != t.end() && it -> l == x) return it;//特判连续段已经完整的情况 -- it;int val = it -> x, l = it -> l, r = it -> r; t.erase(it);t.emplace(l, x - 1, val);//删除原连续段然后插入新连续段 return t.emplace(x, r, val).first;//返回新节点的迭代器 } ``` 扔一个 `insert` 版本： ```cpp inline IT split(int x){ IT it = t.lower_bound(NODE(x, 0, 0)); if(it != t.end() && it -> l == x) return it;//特判连续段已经完整的情况 -- it;int val = it -> x, l = it -> l, r = it -> r; t.erase(it);t.insert(NODE(l, x - 1, val));//删除原连续段然后插入新连续段 return t.insert(NODE(x, r, val)).first;//返回新节点的迭代器 } ``` 我们也说过，珂朵莉树一般用来处理区间推平或类似的问题，下面以推平为例： ```cpp inline void assign(int l, int r, int x){ IT R = split(r + 1), L = split(l); t.erase(L, R);t.emplace(l, r, x); } ``` 是不是十分简单？ ### 0-3 其他函数 当然一个数据结构不可能只有推平，我们可能还需要干一些其他东西。 这里以区间求 `max` 为例，显然我们遍历连续段就行了。 ```cpp inline int query(int l, int r){ int ret = -0x3f3f3f3f; IT R = split(r + 1), L = split(l); for (IT i = L;i != R;++ i) ret = max(ret, it -> val); return ret; } ``` 当然修改或者其他查询也可以用类似的方式，只不过可能需要用上一些叫 `mutable` 的奇怪东西，这不是本文的重点故不多赘述。 可见珂朵莉树实现十分简单。 ### 0-4 简单应用 有一些数据随机的题目用珂朵莉树直接做复杂度是对的。 这不是本文的重点故不多赘述，下面给大家先推荐一道经典题目，建议看完之后再继续往下读。 [CF896C Willem, Chtholly and Seniorious](https://www.luogu.com.cn/problem/CF896C) 用珂朵莉树直接实现即可，代码不放了，反正这道题题解里面也有很详细的实现。 ## 1 应用 ~~重点开始~~ 然而这东西是不是一副暴力的样子。 ~~没错它就是暴力~~ 但是有些时候，在我们对复杂度一番分析之后，会惊奇的发现用珂朵莉树维护一些东西不仅复杂度正确而且十分方便。 下面举一些例子： ### 例1： [P4690 [Ynoi2016] 镜中的昆虫](https://www.luogu.com.cn/problem/P4690) #### 前置知识 CDQ 分治二维数点。 #### 简要题意 区间推平区间数颜色 #### 题解 首先我们考虑单点修改区间数颜色怎么做。 ~~不要跟我说什么带修莫队。~~ 有一个十分~~金典~~经典的套路是记录每一个元素本身以及它的同色前驱的位置，转化为一个二维数点，前驱不在区间内且本身在区间内的点可以产生 $1$ 的贡献，这个用 CDQ分治然后差分一下什么的就行了（没想到吧这是我第一次用CDQ分治二维数点）。 考虑单点修改，我们修改这个位置的前驱，前驱的后继，后继的前驱就行了，然后可以通过加一维时间以及负权点来实现修改。 ~~突然感觉 CDQ 有点强大的啊。~~ 然后我们考虑区间修改。 区间推平？我会暴力珂朵莉树！ 如果你是暴力数颜色的话，你就只能拿 $10\text{pts}$ 。 我们考虑把两种方法结合起来。 这时候有人要问了，这样子的话修改的点数难道不是 $O(nm)$ 的吗？ 考虑对于一次推平，我们在珂朵莉树上的操作是删除一堆同色区间然后插入一个大同色区间，不难发现一个同色中只有 $l$ 节点的位置的前驱不是它本身的“位置 - 1”。 于是我们删除的这些小区间中，我们只需要修改每一个小区间的 $l$ 节点即可！ 显然我们每修改一个 $l$ ，小区间就减少一个，而且由于一个小区间同色，需要修改的“前驱的后继”和“后继的前驱”也都只有一个，而且事实上这里同样用 `std :: set` 维护的话对于每一种颜色可以方便地求出后继，也就是说直接修改后继就行了。 所以每一个区间产生的贡献是 $O(1)$ 的，于是暴力修改的点数变化量是 $O(n+m)$ 。 那么就转化成了若干单点修改和矩形查询，CDQ分治二维数点即可。 本题 $n, m$ 同阶，所以最终复杂度 $O(n\log^2 n)$ 。 ----- 这就是珂朵莉树的强大之处，它可以非常方便地维护连续段，并且配合上其他数据结构就可以保证复杂度。 #### 配套习题1 [CF1136E Nastya Hasn't Written a Legend](https://www.luogu.com.cn/problem/CF1136E) 存在其他做法但可以珂朵莉树实现。 ### 例2：[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)$ 。 ~~比什么二分答案不知道高到哪里去了~~