姓名： 吴苏韬
赛道： 提高组
类型： 算法技能
珂朵莉树/颜色段均摊
关键词： 珂朵莉树、ODT、std::set
由来
珂朵莉树（ \text{Chtholly Tree} ），又称老司机树（ \text{Old Driver Tree} ， \textbf{ODT} ）。
源于 Codeforces Round 449 (Div. 1) 的 C 题 CF896C。
具体实现
注意：珂朵莉树不是数据结构，而是一种颜色段均摊的思想。
核心思想
对于一个区间中值相同的一个子串使用一个结点存储。
结点存储
首先，一个结点需要存储其左右端点，故定义 size_t l, r。
其次，由于将值相同的子串使用一个结点存储，那么结点就需要存储其维护的值，故定义 mutable _Tp w，其中 _Tp 是数据类型。
应该如何将大量结点存储呢？
可以开一个 std::set 存储结点，在看了下文的两个操作后，就可以发现使用 std::set 是最优的，std::vector 更劣。
但是听说 std::vector 因为常数小模板题更快？
代码见后。
一些解释
mutable意为可变的，这样在遍历结点时可以 O(1) 修改迭代器所对应的值，而不用花费 O(\log n) 的时间取出结点，修改后重新插入。- 将小于号如此定义是为了让结点在
std::set中按照原数组中的次序，即按照左右端点次序排列，方便遍历。
结点分裂 / \textbf{split}
\textbf{split} 是珂朵莉树中一个重要的操作，对于给定的一个位置 x\,(x\in[l,r]) ，可以将 [l,r] 分为 [l,x) 和 [x,r] 两个区间，并且返回 [x,r] 区间在 std::set 中的迭代器。
有了这个操作，当对一个结点维护的区间不同位置赋值为不同的值时，就可以将原结点快速拆分了。
例如对区间 [l,r] 的操作，在珂朵莉树上就可以转化成对结点 split(l) \sim split(r+1) 的操作。
应该如何实现 \textbf{split} 操作呢？
-
在
std::set中找到包含 x 的区间对应的结点。可以在
std::set中二分找到结点。根据小于号的定义，可以先使用std::upper_bound找到第一个左端点大于 x 的结点，那么一般前一个结点就是 x\in[l,r] 的区间了。但是存在特殊情况：如果 x 大于区间的右端点，那么说明找不到包含 x 的区间，返回
end()。 -
如果 x=l ，那么就无需分裂，直接返回结点的迭代器即可。
-
记录下当前结点的
l, r, w，然后删除当前节点。 -
添加 [l,x) ，即
insert({l, x - 1, w})。 -
添加 [x,r] ，即
insert({x, r, w})。由于 \textbf{split} 操作需要返回 [x,r] 区间的迭代器，所以返回
insert()返回值的first。冷知识：
insert()函数是由返回值的，且返回值是一个std::pair<std::set<_Tp>::iterator, bool>，第一维表示当前插入数据在集合中的迭代器，第二维表示是否插入成功，即原本是否存在相同的数据。
这样一个结点就成功分裂了。
这里就体现出了 std::set 的优势：插入只需要 O(\log n) 的时间，而线性数据结构需要 O(n) 的时间（包括链表）。
区间推平 / \textbf{assign}
\textbf{assign} 也是一个非常重要的操作，是珂朵莉树时间复杂度正确的保证。
\textbf{assign} 对于给定的区间 [l,r] ，将其全部数赋值为 x 。
首先先 split(r + 1)，然后再 split(l)，分别记录下其迭代器。
Q：为什么要先
split(r + 1)，再split(l)？A：如果先
split(l)，那么返回的迭代器可能会在split(r + 1)的时候失效。
然后删除两个迭代器之间的所有结点（不包括 split(r + 1) 返回的迭代器），然后再将其合并为一个新节点插入 std::set。
复杂度
时间复杂度
如果保证数据随机，那么单次操作的时间复杂度均摊是 O(\log\log n) 的。
但是如果构造数据，那么珂朵莉树的时间复杂度会卡到 O(n^2) 。
所以珂朵莉树一般用于骗分，只要有区间推平操作的题目一般可以得比较多的分数。
我的一位同学在一道好像没有区间推平的题目中用珂朵莉树得了 70 分！
空间复杂度
由于 std::set 最多存储 n 个结点（ n 为序列长度），所以空间复杂度为 O(n) 。
模板代码
只要掌握了这个模板，题目具体分析一下然后暴力就行啦！
template <typename _Tp>
struct ODT_node { // 珂朵莉树的结点
size_t l, r; // 左右端点
mutable _Tp w;
ODT_node(const size_t &_l, const size_t &_r, const _Tp &_w) // 构造函数
: l(_l), r(_r), w(_w) {}
bool operator<(const ODT_node &x) const { // 给结构体定义小于号
if (l != x.l) return l < x.l; // 左端点为第一关键字
if (r != x.r) return r < x.r; // 右端点为第二关键字
return w < x.w; // 存储的值为第三关键字
}
};
template <typename _Tp>
class ODT : public std::set<ODT_node<_Tp>> { // 珂朵莉树直接继承了 std::set，拥有 std::set 的所有 public 的性质以及函数
const size_t INF = 2e9; // 将一个不可能的值作为右端点
public:
auto split(const size_t &x) { // 结点分裂
auto it = --this->upper_bound(ODT_node<_Tp>(x, INF, 0)); // 找到可能包含 x 的区间所对应的结点
if (x > it->r) return this->end(); // 不存在 x
if (it->l == x) return it; // 无需分裂
size_t l = it->l, r = it->r;
_Tp w = it->w; // 记录左右端点以及存储的值
this->erase(it); // 删除当前结点
this->insert(ODT_node<_Tp>(l, x - 1, w)); // 加入 [l,x) 结点
return this->insert(ODT_node<_Tp>(x, r, w)).first; // 加入 [x,r] 结点，并且返回其迭代器
}
void assign(const size_t l, const size_t &r, const _Tp &w) { // 区间推平
auto itr = split(r + 1), itl = split(l); // 得到左右结点
this->erase(itl, itr); // 删除
this->insert(ODT_node<_Tp>(l, r, w)); // 合并为一个结点后插入
}
};
例题分析
Willem, Chtholly and Seniorious
\textbf{Description}
要求实现一种数据结构，维护一个序列 \{a_n\} ，维护如下的操作，操作共 m 次。
1 l r x：将 [l,r] 区间所有数加上 x 。2 l r x：将 [l,r] 区间所有数改成 x 。3 l r x：输出将 [l,r] 区间从小到大排序后的第 x 个数是的多少（不去重）。4 l r x y：输出 \sum^r_{i=l}a_i^x\bmod y 。
n,m\le10^5 ，保证数据随机。
\textbf{Solution}
由于数据随机并且有区间推平操作，故考虑使用珂朵莉树解决。
定义 ODT<lint> tree。
PS：在下文讨论中，默认已经获得了两边的迭代器，即
itl和itr。此外定义了using lint = long long。
操作 1
遍历每个结点，并将其 w 加上给定的值。
void add(size_t l, size_t r, lint w) { // 区间加
auto itr = tree.split(r + 1), itl = tree.split(l);
for (auto it = itl; it != itr; ++it) // 遍历每个结点
it->w += w;
}
操作 2
直接使用 \textbf{assign} 操作即可。
操作 3
可以开一个数组记录下区间内每个数的出现次数。
具体的，定义一个 std::vector，第一维存储数字大小，第二维存储该数字结点维护的区间长度，以方便排序。
遍历节点，然后加入 {it->w, it->r - it->l + 1}。
然后排序。
定义一个 cnt，记录当前已经访问了多少数字。
从前往后遍历 std::vector，然后使 cnt 加上当前的区间长度。
第一次发现 cnt 不小于 x 时，即这个数落在了当前的区间内，返回即可。
lint select(size_t l, size_t r, size_t x) {
auto itr = tree.split(r + 1), itl = tree.split(l);
std::vector<std::pair<lint, size_t>> vec;
for (auto it = itl; it != itr; ++it)
vec.push_back({it->w, it->r - it->l + 1});
std::sort(vec.begin(), vec.end());
size_t cnt = 0;
for (auto it = vec.begin(); it != vec.end(); ++it) {
cnt += it->second;
if (cnt >= x) return it->first;
}
return 1145141919810;
}
操作 4
首先需要实现一个快速幂。
遍历结点，然后结果加上区间长度乘上当前值的 x 次方即可。
lint sum(size_t l, size_t r, lint x, lint y) {
lint res = 0;
auto itr = tree.split(r + 1), itl = tree.split(l);
for (auto it = itl; it != itr; ++it)
(res += (it->r - it->l + 1) * qpow(it->w, x, y)) %= y;
return res;
}
接下来按照题意模拟即可。
qwq