珂朵莉树/颜色段均摊

[Ir1d]

https://oi-wiki.org/misc/odt/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[WhenMelancholy]

inline bool operator(const Node_t &o) const { return l < o.l; } 是不是漏了一个<?

[Hany01]

请问一下为什么先split左端点再split右端点就会RE呢?

[SakiNana7qi]

split右端点的时候可能会使左端点的迭代器失效，亲自测过！

一定要先split右端点，split过右端点后不要忘记重新split左端点！

[StudyingFather]

节点储存这里mutable关键字的含义是不是该解释一下QAQ

[MizukiCry]

@Hany01
请问一下为什么先split左端点再split右端点就会RE呢?

l和r在一个node上时，split(r)会erase这个node再重新插入，导致split(l)的迭代器失效

[EndlessCheng]

也可以使用链表或数组来实现：https://www.luogu.org/blog/endlesscheng/solution-cf896c

[cirnovsky]

感觉讲的不是很清楚

[henrytbtrue]

理理思维好像现在卡珂朵莉树...

[felix-werner]

序列操作似乎把珂朵莉树卡掉了qwq

[ADay526]

建议加上习题loj6284数列分块入门 8

[Legitimity]

脑洞治疗仪那题开始卡 ODT 了 /kk

[shangkelingxiang]

有没有复杂度证明a

[pe200012]

「SCOI2010」序列操作 这道题现在卡 ODT 树了

[seye11]

我觉得split里的第七行应该改为

if (x - 1 >= l) odt.insert(Node_t(l, x - 1, v));

[ffffyc]

这篇文章还是有许多缺漏的啊。

• 首先，应该说明正确名称：颜色段均摊；
• 其次，颜色段均摊也有许多复杂度正确的应用，如用于将 O(n) 区间推平转化成 O(n) 次区间加、配合根号分治以使得段数为 O(sqrt n) 并暴力遍历

感觉可以加几道例题，比如讲讲 CF896C。习题也应加入一些时间复杂度正确的题目，如 P8146 等

[Henry-ZHR]

为什么是 mutable + set 而不是 map 呢

[NanayaHaruki]

这个有java或python实现嘛 ，treeset这种东西虽然有floor来找节点，但左右移动和remove都得再遍历一遍的吗

[Xeuva]

set里的区间是连续且填满整个取值范围的话可以不用维护右端点的值，可以用map直接将左端点映射到该区间的值，整个数据会变成[l1...),[l2...)...这样，指针it指向的区间的范围就是[it->first, next(it)->first)。一开始初始化了数据范围[lo, hi]的左右两个端点后，即[lo...)[hi+1...)，之后可以不用erase，也就不用关心split的顺序了。代码如下(c++)：

struct ChthollyTree {
  int lo, hi;
  map<int, int> T; // {l, v}
  ChthollyTree(int lo=0, int hi=1e9): lo(lo), hi(hi+1) {
    T[lo] = 0; T[hi] = 0;
  }
  auto split(int pos) {
    auto it = prev(T.upper_bound(pos));
    if (it->first == pos) { return it; }
    else { T[pos] = it->second; return next(it); }
  }
  void assign(int l, int r, int v) {
    auto itl = split(l), itr = split(r+1);
    T.erase(itl, itr);
    T[l] = v;
  }
  // int do_something(int l, int r) {
  //   auto itl = split(l), itr = split(r+1);
  //   for (auto it = itl; it != itr; ++it) {
  //     //
  //   }
  // }
};

[YOYO-UIAT]

感觉这个很优雅，比正文里给的优雅多了；而且就算不填满整个取值范围，也可以把没被填的段设成 -1。

[wyc0605]

？