珂朵莉树

致敬传奇出题人lxl

珂朵莉树起源于CF896C ，这道题要求我们实现一种数据结构，可以较快地实现区间和、区间赋值、求区间第 k 大值和求区间 n 次方和。

使用场景

珂朵莉树是一种技巧，而不是一种特定的数据结构，可以用map实现也可以用set等实现，适用于区间赋值操作的数据结构题，在数据随机的情况下复杂度极其优秀，但如果数据不随机且出题人针对数据结构构造了特殊数据，那么复杂度会严重退化。

结构实现(set)

结点定义

struct Node_t {
  int l, r;
  mutable int v;

  Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}

  bool operator<(const Node_t &o) const { return l < o.l; }
};

…………