学习笔记 - 珂朵莉树

珂朵莉树，是一个暴力数据结构。它可用于含有区间赋值的区间维护题目，最好数据随机。其起源于 CF896C。

---

例题：CF896C Willem, Chtholly and Seniorious

请你写一种奇怪的数据结构，支持：

• $1$ $l$ $r$ $x$：将 $[l,r]$ 区间所有数加上 $x$；
• $2$ $l$ $r$ $x$：将 $[l,r]$ 区间所有数改成 $x$；
• $3$ $l$ $r$ $x$：输出将 $[l,r]$ 区间从小到大排序后的第 $x$ 个数是多少（即区间第 $x$ 小，数字大小相同算多次，保证 $1 \leq x \leq r-l+1$）；
• $4$ $l$ $r$ $x$ $y$：输出 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值（即 $(\sum^r_{i=l}a_i^x) \bmod y$）。

数据随机生成。

---

实现

友情提示，代码多用前闭后开区间。

珂朵莉树的核心思想是把一段值相同的区间存成一个块。

块

珂朵莉树使用 set 来维护每个块。

对于每个块，只需要维护其左端点、右端点与其值即可。

struct Node
{
  ull l, r;
  mutable ull v;
  Node(ull _l = 0, ull _r = 0, ull _v = 0): l(_l), r(_r), v(_v) {}
};

bool operator<(Node lhs, Node rhs) { return lhs.l < rhs.l; }

至于为什么有 mutable 一词出现，可以试试不加，会 CE。operator< 是要每个块在 set 中以左端点排序。

核心操作：split

这个操作用于将 $[l,r]$ 的块拆成 $[l,pos-1]$ 与 $[pos,r]$ 的两个块。返回的是 $[pos,r]$ 的迭代器。

struct ChtholyTree
{
  set<Node> nodes;
  set<Node>::iterator split(ull pos)
  {
    set<Node>::iterator i(nodes.lower_bound(Node(pos)));
    if (i != nodes.end() && i->l == pos) return i;
    --i;
    if (i->r <= pos) return nodes.end();
    ull l(i->l), r(i->r), v(i->v);
    nodes.erase(i);
    nodes.insert(Node(l, pos, v));
    return nodes.insert(Node(pos, r, v)).first;
  }
};

首先用 lower_bound，来找到起点大于等于 pos 的最左块。

如果这个块的起点刚好是 pos，显然不需要再分裂，直接 return 即可。

否则，含有 pos 的块就必然是前面一块。

如果此时，pos 依然不在当前块中，显然 pos 必然不合法，返回 end() 迭代器。

当我找到了 pos 的所在块，我们就暴力分裂。将原来的块 erase，将两个新块分别 insert。

set.insert() 返回 pair<iterator, bool>，前者即是我们要的，return 即可。

split 操作是珂朵莉树的核心。它是所有的其它暴力操作的基石。

操作一：区间加

我们只要找到左右两个端点之间的所有块，分别加，即可。

void add(ull l, ull r, ull v)
{
    set<Node>::iterator rp(split(r)), lp(split(l));
    while (lp != rp)
        lp->v += v, ++lp;
}

操作二：区间赋值（推平）

我们将左右两端点之间的所有块全删了，然后添加一个新的大块即可。

void assign(ull l, ull r, ull v)
{
    set<Node>::iterator rp(split(r)), lp(split(l));
    nodes.erase(lp, rp);
    nodes.insert(Node(l, r, v));
}

暴力吧？

操作三：区间第 $k$ 小

将两端点中的每个块抽出来，保留其值与大小。对抽出来的块的值进行排序，从前往后扫，扫到 $k$ 就得出答案。

ull kth(ull l, ull r, ull k)
{
    vector<pair<ull, ull> > rnks;
    set<Node>::iterator rp(split(r)), lp(split(l));
    while (lp != rp)
        rnks.push_back(make_pair(lp->v, lp->r - lp->l)), ++lp;
    sort(rnks.begin(), rnks.end());
    for (vector<pair<ull, ull> >::const_iterator i(rnks.begin()); i != rnks.end(); ++i) {
        if (i->second >= k) return i->first;
        k -= i->second;
    }
    return -1;
}

操作四：区间乘幂求和

对每个块的值使用快速幂，乘该块的大小，求和即可。

ull pow(ull a, ull p, ull b)
{
  ull res(1); a %= b;
  while (p) {
    if (p & 1) res = res * a % b;
    a = a * a % b;
    p >>= 1;
  }
  return res % b;
}

ull pow(ull l, ull r, ull x, ull y)
{
    set<Node>::iterator rp(split(r)), lp(split(l));
    ull res(0);
    while (lp != rp)
        res = (res + (lp->r - lp->l) * ::pow(lp->v, x, y) % y) % y, ++lp;
    return res;
}

细节

注意，对于所有衍生操作，split 的时候一定是先右再左！不然可能会使指针无效。

对于块，注意 mutable 和 operator<。

珂朵莉树在数据比较合理的情况下，跑的很快。同是维护区间数据的数据结构，思维难度比线段树简单，但是时间复杂度不太稳。珂朵莉树的时间复杂度其实比较玄学，如果块太散，是很慢的。有适当的区间推平操作，珂朵莉树才有用。并且，如果数据不随机，也可能卡掉，数据随机会比较稳。

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

struct Node
{
  ull l, r;
  mutable ull v;
  Node(ull _l = 0, ull _r = 0, ull _v = 0): l(_l), r(_r), v(_v) {}
};

bool operator<(Node lhs, Node rhs) { return lhs.l < rhs.l; }

ull pow(ull a, ull p, ull b)
{
  ull res(1); a %= b;
  while (p) {
    if (p & 1) res = res * a % b;
    a = a * a % b;
    p >>= 1;
  }
  return res % b;
}

struct ChtholyTree
{
  set<Node> nodes;
  ChtholyTree() {}
  void addnode(ull l, ull r, ull v) { nodes.insert(Node(l, r, v)); }
  set<Node>::iterator split(ull pos)
  {
    set<Node>::iterator i(nodes.lower_bound(Node(pos)));
    if (i != nodes.end() && i->l == pos) return i;
    --i;
    if (i->r <= pos) return nodes.end();
    ull l(i->l), r(i->r), v(i->v);
    nodes.erase(i);
    nodes.insert(Node(l, pos, v));
    return nodes.insert(Node(pos, r, v)).first;
  }
  void add(ull l, ull r, ull v)
  {
    set<Node>::iterator rp(split(r)), lp(split(l));
    while (lp != rp)
      lp->v += v, ++lp;
  }
  void assign(ull l, ull r, ull v)
  {
    set<Node>::iterator rp(split(r)), lp(split(l));
    nodes.erase(lp, rp);
    nodes.insert(Node(l, r, v));
  }
  ull kth(ull l, ull r, ull k)
  {
    vector<pair<ull, ull> > rnks;
    set<Node>::iterator rp(split(r)), lp(split(l));
    while (lp != rp)
      rnks.push_back(make_pair(lp->v, lp->r - lp->l)), ++lp;
    sort(rnks.begin(), rnks.end());
    for (vector<pair<ull, ull> >::const_iterator i(rnks.begin()); i != rnks.end(); ++i) {
      if (i->second >= k) return i->first;
      k -= i->second;
    }
    return -1;
  }
  ull pow(ull l, ull r, ull x, ull y)
  {
    set<Node>::iterator rp(split(r)), lp(split(l));
    ull res(0);
    while (lp != rp)
      res = (res + (lp->r - lp->l) * ::pow(lp->v, x, y) % y) % y, ++lp;
    return res;
  }
};

struct RandMachine
{
  ull seed;
  RandMachine(ull s): seed(s) {}
  ull operator()()
  {
    ull ret(seed);
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
  }
};

ull read()
{
  ull x(0); char c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x;
}

int main()
{
  const ull N(read()), M(read()), SEED(read()), VMAX(read());
  RandMachine rnd(SEED);
  ChtholyTree tree;
  for (ull i(0); i != N; ++i) {
    tree.addnode(i, i + 1, rnd() % VMAX + 1);
  }
  for (ull op, l, r, x, y, i(0); i != M; ++i) {
    op = rnd() % 4 + 1;
    l = rnd() % N + 1;
    r = rnd() % N + 1;
    if (l > r) swap(l, r);
    if (op == 3) x = rnd() % (r - l + 1) + 1;
    else x = rnd() % VMAX + 1;
    if (op == 4) y = rnd() % VMAX + 1;
    --l;
    switch (op)
    {
    case 1:
      tree.add(l, r, x); break;
    case 2:
      tree.assign(l, r, x); break;
    case 3:
      printf("%llu\n", tree.kth(l, r, x)); break;
    case 4:
      printf("%llu\n", tree.pow(l, r, x, y)); break;
    }
  }
  return 0;
}

练习

P5568 [SDOI2008] 校门外的区间