珂朵莉树 学习笔记
珂朵莉是世界上最幸福的女孩子
先给出一道 C F CF CF 的经典模板题。
CF 896 C Willem, Chtholly and Seniorious
什么是珂朵莉树
又名老司机树 ( O l d (Old (Old D r i v e r Driver Driver T r e e , O D T ) Tree,ODT) Tree,ODT)，是一个玄学暴力数据结构，对于随机数据非常有效。
可以解决什么问题
有一类问题，对一个序列，进行一个区间推平操作。就是把一个范围内，比如 [ l , r ] [l,r] [l,r] 范围内的数字变成同一个。除了推平之外，也可能夹杂着其它操作。如果数据是随机的，就可以用珂朵莉树。
基本原理
对于推平操作结束之后，被推平的区间内的每个数字都是相同的。其实经过若干次推平之后，我们可以看成这个序列上的数字是一段一段的，每一小段里面的数字相同，整个区间由若干个小段组成。
我们定义一个结构体，用一个结构体变量，来表示每个数字相同的段。
struct node{int l,r;//l，r表示这一段的左端点和右端点mutable int v;//v表示这一段上所有元素相同的值是多少//注意前面要加一个mutable，说是能修改，背住就行node(int l,int r=0,int v=0) : l(l),r(r),v(v) {}friend bool operator < (node a,node b) { return a.l < b.l; } //按左端点排序
};
v v v 前面加了 m u t a b l e mutable mutable 关键字，意思是，即使它是个常量，也允许修改 v v v 的值。
当每个数组相同的区间都用一个结构体变量表示之后，我们把这四段插入到一个 s e t set set 里面， s e t set set 会按照每段的左端点进行排序，这样这个序列就排好了。
核心操作 s p l i t split split
在推平进行的过程中，有一些位置被合并到了一个 n o d e node node 里面，但是也有可能一个 n o d e node node 要被拆开，其中的一部分要被改变值。
s p l i t split split 操作就是干这个用的，传的参数是一个位置 p o s pos pos，以 p o s pos pos 为界去分割，找到一个包含 p o s pos pos 的区间，把它分成 [ l . p o s − 1 ] [l.pos-1] [l.pos−1] 和 [ p o s , r ] [pos,r] [pos,r] 两半。如果 p o s pos pos 是一段区间的开头，就不用分割了，直接返回这个区间。
set<node> s;
set<node>::iterator split(int pos){set<node>::iterator it = s.lower_bound(pos);if(it != s.end() && it->l == pos) return it;it--;if(it->r < pos) return s.end();int l = it->l;int r = it->r;int v = it->v;s.erase(it);s.insert(node(l,pos-1,v)); //返回一个pair，其中的first是新插入节点的迭代器return s.insert(node(pos,r,v)).first;
}
这个 s e t set set 就是装 n o d e node node 的集合，用 l o w e r lower lower b o u n d bound bound 函数返回第一个大于等于参数的位置，返回的是一个迭代器。我们去查询这个 p o s pos pos 对应的 l o w e r lower lower b o u n d bound bound，找到这个 i t it it 的位置。有三种情况。
- 如果正好找到了一段区间，是以 p o s pos pos 开头的，对应代码中的第一个 i f
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！