珂朵莉树

名称简介¶

老司机树，ODT(Old Driver Tree)，珂朵莉树（Ctholly Tree)。
起源自CF896C。

前置知识¶

会用 STL 的 set 就行。

核心思想¶

把值相同的区间合并成一个结点保存在 set 里面。

用处¶

骗分。
只要是有区间赋值操作的数据结构题都可以用来骗分。
一般出题人不会刻意卡，但是不小心卡了就……

如果要保证复杂度正确，必须保证数据随机。
证明在此。

正文¶

首先，结点的保存方式：

struct node {
  int l, r;
  mutable int v;
  inline bool operator(const node &o) const { return l < o.l; }
};

其中， int v 是你自己指定的附加数据。

然后，我们定义一个 set<node> odt; 来维护这些结点。
为简化代码，可以 typedef set<node>::iterator IT 。

split¶

最核心的操作之一 split ，它用于取得以开头的结点。
参考代码如下：

IT split(int x) {
  if (x > n)
    ;
  return odt.end();
  IT it = --odt.upper_bound((node){x, 0, 0});
  if (it->l == x) return it;
  int l = it->l, r = it->r, v = it->v;
  odt.erase(it);
  odt.insert((node){l, x - 1, v});
  return odt.insert((node){x, r, v}).first;
}

这个玩意有什么用呢？
任何对于的区间操作，都可以转换成 set 上的操作。

assign¶

另外一个重要的操作 assign 用于对一段区间进行赋值。
对于 ODT 来说，区间操作只有这个比较特殊，也是保证复杂度的关键。
如果 ODT 里全是长度为的区间，就成了暴力，但是有了 assign ，可以使 ODT 的大小下降。
参考代码如下：

void assign(int l, int r, int v) {
  IT itr = split(r + 1), itl = split(l);
  odt.erase(itl, itr);
  odt.insert((node){l, r, v});
}

其他操作¶

套模板就好了，参考代码如下：

void performance(int l, int r) {
  IT itr = split(r + 1), itl = split(l);
  for (; itl != itr; ++itl) {
    // Perform here
  }
}

习题¶

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用