吾日三省吾身：末日时在干什么？有没有空？可以来拯救一下吗？算法思想非常简单：就是暴力。对于数据结构题，我们有这样一种思路去维护：对于一个数列，我们把不同的数字看成不同的颜色段，然后对每个颜色段进行暴力操作，可以有效降低时间复杂度。但这种暴力是很好卡掉的，只需让颜色段尽可能多，算法

经典题（珂朵莉树的诞生）：https://www.luogu.com.cn/problem/CF896C参考：https://www.luogu.com.cn/article/yfcae6d6不用知道它的具体复杂度，主要是学习如何实现。珂朵莉树（ChthollyTree），又名老司机树ODT（OldDriverTree）。splitpos区间分割操作，也就是将包含pos的区间分割为两端

大家好，我喜欢珂朵莉树，所以我用珂朵莉树\(AC\)了本题。实际上，我们比较容易发现，这题实际上就是求\([l,r]\)中的所有点作为关键点时，虚树所压缩的所有点（实际上就是显现出来的点+在虚边上的点）。那么我们容易发现，一个点\(x\)作为虚树所压缩的所有点的充要条件为：\(x\)是至少

珂朵莉树是基于set的数据结构，与线段树、平衡树等树形结构类似，珂朵莉树是用来解决区间问题的很暴力的树形结构该数据结构支持区间推平，即将区间\([l,r]\)赋值为同一个值1.前置知识setset本质是平衡树，所以不会出现重复的元素且会自动排序，部分函数：set<Node>t;//定

前言珂朵莉树（ChthollyTree），又名老司机树（OldDriverTree），起源自CF896CWillem,ChthollyandSeniorious。严格来说，珂朵莉树这种想法是基于数据随机的颜色段均摊，而不是一种数据结构，可作为一些题目的暴力做法（因此原题被分到了暴力数据结构的标签），在随机数据下一般效率较高。基

这是即将推送到OI-wiki的，对于原OI-wiki珂朵莉树页面的重构。作者是我。感谢上一位维护这玩意的人。简介珂朵莉树（ChthollyTree），又名老司机树ODT（OldDriverTree）。起源自CF896C。这个名称指代的是一种“使用平衡树（std::set、std::map等）或链表（std::list、手写链表等）维护颜

对于一个序列，它有较多重复元素，并且题目需要维护区间修改，维护区间信息，维护整块值域信息的，那么就可以考虑珂朵莉树解决.主要思想珂朵莉树将全部相同的颜色块压缩为一组，如对于下述序列：111234444珂朵莉树铺平后即可以变为这样：{1,3,1}{4,4,2}{5,5,3}{6,9,4}其中的三

介绍珂朵莉树，学名珂朵莉树，又学名老司机树（$ODT$），常用来解决“区间推平”（把区间改为某一个数）等的操作，只适用于随机数据，可以定向卡掉；其实这玩意就是暴力，没啥可说的，分块都比不上她暴力；但人家毕竟是她，所以对于一些题还是有用的；实现只要你会$C++\STL$里的$set$，搞定她完

珂朵莉树这个名字我猜是来源于初次诞生这个算法的题目->Willem,ChthollyandSeniorious算法适用于数据随机，并且有区间推平操作，也就是区间赋值操作，就可以用set维护，达到优秀的\(O(nlogn)\)时间复杂度。定义structNode{ intl,r; mutableintv; Node(intl,intr

一种特殊的数据结构。介绍李欣隆发明。本质上并不是一种树形数据结构，思想是把一个区间按\(value\)划分成不少的小区间，然后暴力操作。显然，这样做的复杂度完全依赖于小区间的多少，所以复杂度需要由区间推平操作保证。在随机的数据下，可以证明每次的小区间期望有\(\log_2n\)个，

构造set：structnode{intl,r;mutableintv;node(intl,intr,intv=0):l(l),r(r),v(v){}booloperator<(constnode&a)const{returnl<a.l;}};set<node>s;分裂set：autosplit(intpos){aut

简介珂朵莉树一般多见于区间推平操作，即把[l,r]区间的值都赋值成k值的区间推平操作，在数据随机中可以出现奇效。模板点击查看代码structnode{intl,r;mutableintv;//mutable相反于const用于操作存于set（存于set的均为const，但是加了mutable即可修改其值）中的值.

前言大家都打过CF，而对于CF特殊的赛制，大家也有所耳闻。其中最激动人心的环节也就是Hack环节了。其实赛时捏数据，也无非就是对着自己的代码定向爆破罢了。多捏边界条件，例如询问总是询问修改的边界，再或者题目中某操作可能的特殊性质。多捏特殊的图，有的图因为其特殊的性质，对复

目录0x00：介绍1x00：思想1x01：节点保存1x02：核心操作split1x03：推平操作assign2x00：例题2x01：CF896C2x02：CF915E3x00：总结0x00介绍珂朵莉树（ChthollyTree），又称ODT（OldDriverTree），一种数据结构，但似乎暴力到不能称之为数据结构。可以很好地骗分，在随机数据下十分有效，常用于将\([l

珂朵莉树的适用范围是具有区间赋值操作且数据随机的题目。珂朵莉树的思想在于随机数据下的区间赋值操作很可能让大量元素变为同一个数，所以我们以三元组<l,r,v>的形式保存数据（区间[l,r]中的元素的值都是v）：structnode{lll,r;mutablellv;//这里mutable要写不然

柯学家——珂朵莉树学习笔记珂朵莉树（ChthollyTree），又名老司机树ODT（OldDriverTree）。起源自lxl的CF896CWillem,ChthollyandSeniorious。前置知识：std::set。思想将区间用set维护，每次对一个区间进行操作的时候，就将这个区间分离（split）出来。复杂度的保证依靠推平

珂朵莉树的复杂度分析CF896C珂朵莉树起源题LG4979矿洞：坍塌珂朵莉树可以在区间覆盖时顺便把左右的同色段合并了，这样任意时刻相邻的两段都不同色本题询问时判断\([l,r]\)是否同色就可以通过判断\([l,r]\)是否在同一段实现了https://www.luogu.com.cn/problem/P8146

珂朵莉树引入珂朵莉树(ChthollyTree)，又名老司机树(OldDriverTree)。起源于CF896C。这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。前置需要了解STL的set的基本用法。比如：insert(x) 当容器中没有等价元素的时候，将元素x插入到 set 中。er

处理区间赋值问题的神器！珂朵莉树的实现非常简单（baoli）,建树时把区间的左右端点和权值作为一个节点全扔到std::set（或者链表）中维护即可split:核心操作之一,将一段区间提取出来，在此之上进行一些操作assign:核心操作之二，也是降低珂朵莉树时间复杂度的重要操作，把一段区间推平赋值，

区间赋值的数据结构都可以骗分，在数据随机的情况下，复杂度可以保证。时间复杂度：O（nloglogn）structODT{ structnode{ intl,r; mutableLLv; node(intl,intr=-1,LLv=0):l(l),r(r),v(v){} booloperator<(constnode&o)const{returnl<o.l;} }; s

P4690[Ynoi2016]镜中的昆虫题解题意维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。将区间 \([l,r]\) 的值修改为 \(x\)。询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。题解感觉这道题还是比较有意思的,像是一堆套路

##什么是珂朵莉树？**珂朵莉树**，别名颜色段均摊、ODT，它是$2017$年一场CF比赛中提出的数据结构，因为题目背景主角是《末日时在做什么？有没有空？可以来拯救吗？》的主角珂朵莉，

珂朵莉树浅析0.关于珂朵莉中国珂学院1.珂朵莉树实现珂朵莉树（也称OldDriverTree），是一种暴力数据结构，其代表的操作有：区间推平（将区间\([l,r]\)的数修改为\(x\)）；

严格来说，珂朵莉树主要的用处是骗分——OIWikiclassODT{structnode{intl,r;mutablellv;node(constint&il,constint&ir,

珂朵莉最可爱了。好了不废话了，直接开始珂朵莉树。什么是珂朵莉树珂朵莉树，又叫老司机树，英文名字\(\text{ODT}\)，是一种支持区间平推的乱搞数据结构，在数据随机时表现十分