珂朵莉树 学习笔记

珂朵莉是世界上最幸福的女孩子

先给出一道 $CF$ 的经典模板题。

CF 896 C Willem, Chtholly and Seniorious

什么是珂朵莉树

又名老司机树$(Old$ $Driver$ $Tree,ODT)$，是一个玄学暴力数据结构，对于随机数据非常有效。

可以解决什么问题

有一类问题，对一个序列，进行一个区间推平操作。就是把一个范围内，比如 $[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$ 前面加了 $mutable$ 关键字，意思是，即使它是个常量，也允许修改 $v$ 的值。

当每个数组相同的区间都用一个结构体变量表示之后，我们把这四段插入到一个 $set$ 里面，$set$ 会按照每段的左端点进行排序，这样这个序列就排好了。

核心操作 $split$

在推平进行的过程中，有一些位置被合并到了一个 $node$ 里面，但是也有可能一个 $node$ 要被拆开，其中的一部分要被改变值。
$split$ 操作就是干这个用的，传的参数是一个位置 $pos$，以 $pos$ 为界去分割，找到一个包含 $pos$ 的区间，把它分成 $[l.pos-1]$ 和 $[pos,r]$ 两半。如果 $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;
}

这个 $set$ 就是装 $node$ 的集合，用 $lower$$bound$ 函数返回第一个大于等于参数的位置，返回的是一个迭代器。我们去查询这个 $pos$ 对应的 $lower$$bound$，找到这个 $it$ 的位置。有三种情况。

1. 如果正好找到了一段区间，是以 $pos$ 开头的，对应代码中的第一个 i