珂朵莉树 - OI Wiki - Githubissues

Ir1d commented 5 years ago

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

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

WhenMelancholy commented 5 years ago

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

Hany01 commented 5 years ago

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

SakiNana7qi commented 5 years ago

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

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

StudyingFather commented 5 years ago

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

MizukiCry commented 5 years ago

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

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

EndlessCheng commented 4 years ago

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

cirnovsky commented 4 years ago

感觉讲的不是很清楚

henrytbtrue commented 4 years ago

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

felix-werner commented 4 years ago

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

ADay526 commented 4 years ago

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

Legitimity commented 3 years ago

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

shangkelingxiang commented 3 years ago

有没有复杂度证明a

pe200012 commented 3 years ago

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

seye11 commented 2 years ago

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

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

ffffyc commented 2 years ago

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

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

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

Henry-ZHR commented 2 years ago

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

NanayaHaruki commented 2 years ago

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

Xeuva commented 2 years ago

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) {
  //     //
  //   }
  // }
};

OI-wiki / gitment

珂朵莉树 - OI Wiki #280