(整活向,内容正经wwww)
为什么随机区间能被几张颜色卡片维护?
这期讲 `Chtholly Tree / Old Driver Tree / ODT`:一种用有序集合维护等值连续段的区间技巧。
它能在随机数据和频繁区间赋值下,把很多散点压缩成少量颜色段,从而处理区间加、区间赋值、区间第 k 小和区间幂和。但它不是最坏情况有保证的万能结构,对抗数据会让段数变大。
本期内容包括:
- CF896C 和“珂朵莉树”命名背景
- 颜色段维护的定义和不变量
- `split(pos)` 与 `assign(l,r,x)` 的逐步动画
- 区间加、第 k 小、幂和取模如何复用完整段
- 随机数据下为什么快,以及什么时候不该用
- `std::set` / `std::map` 代码骨架