珂朵莉树

珂朵莉树，又称Old Driver Tree(ODT)（老司机树），是一种基于std::set的暴力数据结构。

由数据结构大师lxl发明

适用范围

在数据随机的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。

时空复杂度

珂朵莉树的复杂度是由assign_val保证的。

由于数据随机，有1/4的操作为assign，并且大部分点会被缩成整块的区间，需要操作的次数很少。

set的大小快速下降，最终趋于loglogn ，使得这种看似暴力无比的数据结构复杂度接近O(mloglogn)

引用

洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C

讲解 https://www.bilibili.com/video/av21651173

练习

https://www.luogu.com.cn/problem/CF896C

https://www.luogu.com.cn/problem/CF915E（复杂度为最高nlogn,即非暴力）

https://www.luogu.com.cn/problem/P5444

https://www.luogu.com.cn/problem/CF1567E（复杂度为最高nlogn,即非暴力）

https://darkbzoj.tk/problem/1858（洛谷上此题数据加强，珂朵莉树无法通过）

总结

珂朵莉树，大部分时候可以作为一种骗分手段，有时也可以作为正解出现。