ODT

好题，牛牛的一个套路。 先树剖一下，我们可以很简单的用树状数组维护每个点的真实值。 对于每个点只维护所有轻儿子的信息，对于每次询问的时候暴力加入当前点，重儿子以及父亲的信息，查询第 \(k\) 大，再删除信息即可。 考虑链修改的影响。因为只维护的是轻儿子的信息，那么只有链上的所有轻边会修改。 具体的 ......

珂朵莉树 ODT 来源 CF896C 适用范围 是一种支持以下操作的暴力算法: 区间修改 区间赋值 求区间内的第 \(k\) 小 求区间 \(k\) 次方和 ODT 本质上是建立在区间赋值的一种操作，有区间赋值的操作的话可以保证时间复杂度均摊为 \(O(n \log \log n)\)，但是如果没有 ......

（珂朵莉图压压惊） 适用场景：不断区间修改、区间询问，数据随机 ODT：old driver tree（老司机树），又名珂朵莉树，是一个骗分的好东西。其内部是基于 std::set 实现的，而 std::set 是基于红黑树实现的，所以我觉得应该是算法，但是对于ODT究竟是算法还是数据结构有争议。 ......

#### 处理区间赋值问题的神器！ 珂朵莉树的实现非常简单（baoli）,建树时把区间的左右端点和权值作为一个节点 全扔到`std::set`（或者链表）中维护即可 **split**: 核心操作之一,将一段区间提取出来，在此之上进行一些操作 **assign**: 核心操作之二，也是降低珂朵莉树时 ......

$\color{#52C41A}{\text{染}}\color{#E74C3C}{\text{色}}\color{#52C41A}{\text{数}}\color{#E74C3C}{\text{组}}$ ......

题面传送门 还是见识太少了。 直接算颜色个数不好算，因为是和式，所以考虑计算某个颜色的贡献。 对于某个时刻，有一些位置是当前时刻，那么设所有没有这些位置的联通块平方和为 $S$ ，则贡献为 $n^2-S$。 因为总共有效的修改只有 $O(m)$ 个，因此我们需要支持：改变一个点的状态，查询为 $1$ ......

梗出处：请问您今天要来点兔子吗？ 这篇文章主要记录一下自己学习 $\text{ODT}$ 发生的种种。 CF896C Willem, Chtholly and Seniorious $\text{ODT}$ 成名题目，表示 $\text{lxl}$ 为了防 $\text{Hack}$ 真的是用心了。 ......