写在前面

珂朵莉树就是说珂朵莉种的树
珂朵莉(Chtholly·Nota·Seniorious)是一名成体妖精兵

珂朵莉树是什么

珂朵莉树是一种数据结构
珂朵莉树,又名老司机树,简称ODT,是一种可以用来把一段区间拍扁推平的数据结构
珂朵莉树是一种基于set这个stl的数据结构

珂朵莉树的操作

1.定义一个节点

这个结构体是珂朵莉树的一个节点
其中的l,r是这个节点代表的区间端点
val是这个节点的权值 其中的mutable是可变换的意思
如果不可变换的话后面的add操作就会有锅
后面我们再说
然后我们把这些节点存在一个set里面 就看成是建树了
2.接下来的操作就是珂朵莉树的核心操作了:split操作
代码长成这样

这个操作的意思就是字面意思 分离一段区间
代码里面的IT是我的宏定义 包括下文的IT 都是
这个set的迭代器
这个东西返回的是一个迭代器
听我讲这个操作
首先我再这个集合找到pos这个元素的lower_bound的位置
然后如果不用切割 直接返回就行了
不然的话我们用迭代器it找到pos的迭代器
先删除原来的区间
然后我们把这个元素前面的部分(L,pos-1)作为一个区间插入
然后把后面的部分(pos,R)插入
返回的是后面区间左端点的迭代器
set的insert操作返回一个iterator,bool的pair,我们只拿走第一个。
也就是我们的返回值
看来我们在这个操作里面什么实质性的事情都没有做(把元素删除又插入了),但是在这个过程中我们去到了我们需要的东西:后半段区间的迭代器,能做什么我们一会再说
3.下一个核心的操作是assign操作,这个操作是区间赋值

这个操作太暴力了
首先是把l,r这段区间提取出来
然后暴力把原来这段区间删除,最后我们把新的区间加入
区间左右不变,权值变化
4.add操作
这个太暴力了
我们把区间提取出来 然后每个位置暴力修改

5.查询k小
这个也很暴力 我们把所有的东西拿出来 然后放到一个vector里面
我们把这个vector内部的所有元素排个序就行了

6.珂朵莉树专属操作 求区间k次方的和
这个的话当然是非常简单了。。
没错就是暴力。。。
我们把这个区间取出来 然后暴力求k次方加起来就行了
这个最好的地方就是我们可以求出任意的区间
但是在线段树上面我们不好维护

有关珂朵莉树的缺点

珂朵莉树由于是暴力拆开和合并区间
所以说这个时间复杂度不好
最差的时间复杂度就是我们一直让他assign
所以说这个的复杂度就会很高
不过当题目里面保证数据随机或者真的你没有什么做法的时候
珂朵莉树其实是个挺好的选择
数据证明一般的话这个时间复杂度是$O(mlogn)$
但是面对构造的数据可能时间复杂度会高达$O(nm)$
不过嘛
我永远喜欢珂朵莉233333