|
|
| 第2行： |
第2行： |
|
| |
|
| 由数据结构大师lxl发明 | | 由数据结构大师lxl发明 |
|
| |
| ===适用范围===
| |
| 在'''{{color|red|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。
| |
|
| |
|
| ==='''时空复杂度'''=== | | ==='''时空复杂度'''=== |
| 珂朵莉树的复杂度是由assign_val保证的。
| | 瑟尼欧里斯树的复杂度是严格O(n√n)的。 |
| | |
| 由于数据随机，有1/4的操作为assign，并且大部分点会被缩成整块的区间，需要操作的次数很少。
| |
| | |
| set的大小快速下降，最终趋于loglogn ，使得这种看似暴力无比的数据结构复杂度接近O(mloglogn)
| |
|
| |
|
| ==引用== | | ==引用== |
| 洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C
| | 原题 http://codeforces.com/problemset/problem/896/E |
| | |
| 讲解 https://www.bilibili.com/video/av21651173
| |
| | |
| <big>'''练习'''</big>
| |
| | |
| https://www.luogu.com.cn/problem/CF896C
| |
| | |
| https://www.luogu.com.cn/problem/CF915E<nowiki/>（复杂度为最高nlogn,即非暴力）
| |
| | |
| https://www.luogu.com.cn/problem/P5444
| |
|
| |
|
| https://www.luogu.com.cn/problem/CF1567E<nowiki/>（复杂度为最高nlogn,即非暴力） | | 卡常加强版 https://www.luogu.com.cn/problem/P4117 |
|
| |
|
| https://darkbzoj.tk/problem/1858<nowiki/>（洛谷上此题数据加强，珂朵莉树无法通过）
| |
|
| |
|
| == 总结 == | | ==总结== |
| 珂朵莉树，大部分时候可以作为一种骗分手段，有时也可以作为正解出现。
| | '''瑟尼欧里斯树作为广大分块之一，非常毒瘤。''' |
