瑟尼欧里斯树：修订间差异
无编辑摘要 |
无编辑摘要 |
||
| 第3行： | 第3行： | ||
由数据结构大师lxl发明 | 由数据结构大师lxl发明 | ||
< | ===适用范围=== | ||
在'''{{color|red|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。 | |||
==='''时空复杂度'''=== | |||
珂朵莉树的复杂度是由assign_val保证的。 | |||
由于数据随机，有1/4的操作为assign，并且大部分点会被缩成整块的区间，需要操作的次数很少。 | |||
set的大小快速下降，最终趋于loglogn ，使得这种看似暴力无比的数据结构复杂度接近O(mloglogn) | |||
==引用== | |||
洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C | |||
讲解 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://darkbzoj.tk/problem/1858<nowiki/>（洛谷上此题数据加强，珂朵莉树无法通过） | |||
== 总结 == | |||
珂朵莉树，大部分时候可以作为一种骗分手段，有时也可以作为正解出现。 | |||
2022年3月17日 (四) 19:27的版本
瑟尼欧里斯树，是算法第二分块的别称，名字来源是CF896E。
由数据结构大师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（洛谷上此题数据加强，珂朵莉树无法通过）
总结
珂朵莉树，大部分时候可以作为一种骗分手段，有时也可以作为正解出现。