珂朵莉树学习笔记

🚀 优质资源分享 🚀

0x00 前言

0x01 关于其命名

最开始出现在 Codeforces Round #449 (Div. 1) C题 上，这位珂学家在题解中用了一种玄学的数据结构解题，开始命名为 ODT树（Old Driver Tree，老司机树，以出题者的ID命名），后来普遍称为珂朵莉树。

0x02 能解决的问题

珂朵莉树用于解决含有区间平推操作（即将区间上的数全部变为一个数）的问题时卓有成效，在数据随机的情况下，用 set 实现复杂度为 O(N log log N)O(N \ log \ log \ N)，用链表实现复杂度为 O(N log N)O(N \ log \ N)，比同类问题其他算法更优。时间复杂度证明请移步这篇文章。

0x03 前置知识

• set 相关知识

0x10 正文

本文使用 Codeforces Round #449 (Div. 1) C题 作为例题讲解珂朵莉树。

0x11 题意

– 威廉…
– 怎么了？
– 瑟尼欧里斯好像出了什么问题…
– 我会看看的…

瑟尼欧里斯是一把由特殊护符按特定顺序排列组成的剑。
已经 500500 年过去了，现在剑的状态很差，所以威廉决定检查一下。
瑟尼欧里斯由 nn 片护符组成，威廉把它们排成一列，每个护符上有一个数字 aia_i。
为了保养它，威廉需要进行 mm 次操作。
这里有四种操作：

• 1 l r x1 \ l \ r \ x : 将区间 [l,r][l, r] 上的数加上 xx。
• 2 l r x2 \ l \ r \ x : 将区间 [l,r][l, r] 上的数全部变为 xx。
• 3 l r x3 \ l \ r \ x : 查询区间 [l,r][l, r] 的第 xx 大数。
<