珂朵莉树 - 版本历史

Xueyijie：/* 时空复杂度 */

2021-11-28T08:52:42Z

时空复杂度

←上一版本		2021年11月28日 (日) 16:52的版本
第1行：		第1行：
	'''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。		'''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。

			由数据结构大师lxl发明

	===适用范围===		===适用范围===
	在'''{{color\|red\|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。		在'''{{color\|red\|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。

	=== '''时空复杂度''' ===		==='''时空复杂度'''===
	珂朵莉树的复杂度是由assign_val保证的。		珂朵莉树的复杂度是由assign_val保证的。

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

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

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

	讲解 https://www.bilibili.com/video/av21651173		讲解 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/>（洛谷上此题数据加强，珂朵莉树无法通过）

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

2020年7月7日 (二) 14:32 HGGG

2020-07-07T14:32:12Z

←上一版本		2020年7月7日 (二) 22:32的版本
第1行：		第1行：
	'''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。		'''珂朵莉树'''，又称Old Driver Tree(ODT)<s>（老司机树），</s>是一种基于std::set的'''暴力'''数据结构。

	=== 适用范围 ===		===适用范围===
	在'''{{color\|red\|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。		在'''{{color\|red\|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。

	'''时空复杂度'''		=== '''时空复杂度''' ===

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

	由于数据随机，有1/4的操作为assign。		由于数据随机，有1/4的操作为assign。

	set的大小快速下降，最终趋于logn ~~，使得这种看似暴力无比的数据结构复杂度接近mlogn 。~~		set的大小快速下降，最终趋于logn ，使得这种看似暴力无比的数据结构复杂度接近O(mlogn)
	~~<br~~ />
			== 引用 ==
			洛谷题解 https://www.luogu.com.cn/problem/solution/CF896C

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

HGGG：/* 适用范围 */

2020-07-07T09:42:34Z

适用范围

新页面

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

=== 适用范围 ===
在'''{{color|red|数据随机}}'''的情况下，要求对一段区间内的数据进行统一赋值（推平）操作。

'''时空复杂度'''

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

由于数据随机，有1/4的操作为assign。

set的大小快速下降，最终趋于logn ，使得这种看似暴力无比的数据结构复杂度接近mlogn 。
<br />

珂朵莉树 - 版本历史

Xueyijie：​/* 时空复杂度 */

2020年7月7日 (二) 14:32 HGGG

HGGG：​/* 适用范围 */

Xueyijie：/* 时空复杂度 */

HGGG：/* 适用范围 */