珂朵莉树 (Chtholly Tree / ODT) 讲稿

~ 2026-5-24 8:40:57

珂朵莉树 (Chtholly Tree / ODT) 讲稿

一、背景与命名

珂朵莉树（又称 老司机树，Old Driver Tree，简称 ODT）并非一种严格意义上的树形数据结构。它的名字来源于 Codeforces 题目 CF 896C - Willem, Chtholly and Seniorious，题目中三个角色分别出自动画《末日时在做什么？有没有空？可以来拯救吗？》（简称 SukaSuka）。

该题要求实现四种操作——区间加、区间赋值、区间第 k 小、区间幂次和，且数据随机生成。使用者发现，由于大量区间赋值操作的存在，数组中的不同值段会迅速减少，因此用一个 std::set 维护值段即可高效通过。为纪念此题，这种数据结构被称为"珂朵莉树"。

二、核心思想

2.1 存储结构

将数组表示为若干连续且值相同的区间。每个区间是一个三元组 (l, r, val)：区间 [l,r][l, r] 内所有元素的值均为 val。

用 std::set 按区间左端点排序存储：

struct Node {
    int l, r;
    mutable long long val;
    bool operator<(const Node &o) const { return l < o.l; }
};
set<Node> odt;

mutable 关键字允许在 const 成员函数中修改 val，因为 set 中的元素会被视为 const。

2.2 关键操作：split(pos)

将包含位置 pos 的区间 [L,R][L,R] 分裂为 [L,pos−1][L, pos-1] 和 [pos,R][pos, R]，并返回指向后者的迭代器。

auto split(int pos) {
    auto it = odt.lower_bound({pos, 0, 0});
    if (it != odt.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    long long V = it->val;
    odt.erase(it);
    odt.insert({L, pos - 1, V});
    return odt.insert({pos, R, V}).first;
}

示意图：

Before split(4):   [1,3]:5   [4,7]:3   [8,10]:2
After  split(4):   [1,3]:5   [4,7]:3   [8,10]:2   (左端点在 4 无需分裂)

Before split(5):   [1,3]:5   [4,7]:3   [8,10]:2
After  split(5):   [1,3]:5   [4,4]:3   [5,7]:3   [8,10]:2

split 是所有区间操作的基础。先 split(r+1)，再 split(l) 可以安全地获取 [l,r][l, r] 范围内的所有区间。

2.3 核心操作：assign(l, r, val)

区间赋值——将 [l,r][l, r] 内所有元素赋为新值 val。这是 ODT 保持高效的关键！

void assign(int l, int r, long long val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, val});
}

每次 assign 会将 [l,r][l, r] 内的多个区间合成为一个，大幅减少区间总数。

三、常用区间操作模板

在 split(l) 和 split(r+1) 之后，遍历 [itl, itr) 即可处理范围内每一个值段：

void add(int l, int r, long long x) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it)
        it->val += x;
}

long long sum(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    long long res = 0;
    for (auto it = itl; it != itr; ++it)
        res += it->val * (it->r - it->l + 1);
    return res;
}

long long kth(int l, int r, int k) {
    auto itr = split(r + 1), itl = split(l);
    vector<pair<long long, int>> v;
    for (auto it = itl; it != itr; ++it)
        v.push_back({it->val, it->r - it->l + 1});
    sort(v.begin(), v.end());
    for (auto &p : v) {
        k -= p.second;
        if (k <= 0) return p.first;
    }
    return -1;
}

四、复杂度分析

情况 复杂度
随机数据 + 大量 assign 期望 O(mlog⁡n)O(m \log n)
仅有区间加/查询 退化至 O(nm)O(nm)
构造卡 ODT 数据 O(nm)O(nm) — 可被 Hack

为什么随机数据下高效？

  1. assign 操作每次至少将 ≥2\ge 2 个区间合为 1 个，区间总数快速收敛至 O(1)O(1)。
  2. 在随机数据下，期望区间数约为 O(log⁡n)O(\log n) 或 O(n)O(\sqrt{n})。
  3. 每次 split 最多增加 1 个区间。

使用条件（三个缺一不可）

  • 有区间赋值操作
  • 数据随机生成（或题目明确不卡 ODT）
  • 不会故意构造让区间数不减少的数据

五、完整模板

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

struct Node {
    int l, r;
    mutable long long val;
    bool operator<(const Node &o) const { return l < o.l; }
};

struct ODT {
    set<Node> s;

    auto split(int pos) {
        auto it = s.lower_bound({pos, 0, 0});
        if (it != s.end() && it->l == pos) return it;
        if (it == s.begin()) return s.end();
        --it;
        int L = it->l, R = it->r;
        long long V = it->val;
        s.erase(it);
        s.insert({L, pos - 1, V});
        return s.insert({pos, R, V}).first;
    }

    void assign(int l, int r, long long val) {
        auto itr = split(r + 1), itl = split(l);
        s.erase(itl, itr);
        s.insert({l, r, val});
    }

    void add(int l, int r, long long x) {
        auto itr = split(r + 1), itl = split(l);
        for (auto it = itl; it != itr; ++it)
            it->val += x;
    }

    long long query_sum(int l, int r) {
        auto itr = split(r + 1), itl = split(l);
        long long res = 0;
        for (auto it = itl; it != itr; ++it)
            res += it->val * (it->r - it->l + 1);
        return res;
    }
};

六、经典例题

例题 1：CF 896C — Willem, Chtholly and Seniorious

【题意】

维护一个长度为 nn 的数组，支持四种操作（所有数据随机生成）：

  1. 1 l r x：将 [l,r][l, r] 内所有元素加上 xx
  2. 2 l r x：将 [l,r][l, r] 内所有元素赋值为 xx
  3. 3 l r x：求 [l,r][l, r] 内第 xx 小的数
  4. 4 l r x y：求 ∑i=lraix mod y\sum_{i=l}^r a_i^x \bmod y

n,m≤105n, m \le 10^5，数据随机。

【思路】

标准 ODT 板题。四种操作均可直接套用区间遍历模板。

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

const i64 MOD = 1000000007;

i64 qpow(i64 a, i64 b, i64 mod) {
    a %= mod;
    i64 res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

struct Node {
    int l, r;
    mutable i64 val;
    bool operator<(const Node &o) const { return l < o.l; }
};
set<Node> odt;

auto split(int pos) {
    auto it = odt.lower_bound({pos, 0, 0});
    if (it != odt.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    i64 V = it->val;
    odt.erase(it);
    odt.insert({L, pos - 1, V});
    return odt.insert({pos, R, V}).first;
}

void assign(int l, int r, i64 val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, val});
}

void add(int l, int r, i64 x) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it)
        it->val += x;
}

i64 kth(int l, int r, int k) {
    auto itr = split(r + 1), itl = split(l);
    vector<pair<i64, int>> v;
    for (auto it = itl; it != itr; ++it)
        v.push_back({it->val, it->r - it->l + 1});
    sort(v.begin(), v.end());
    for (auto &p : v) {
        k -= p.second;
        if (k <= 0) return p.first;
    }
    return -1;
}

i64 sum_pow(int l, int r, i64 x, i64 y) {
    auto itr = split(r + 1), itl = split(l);
    i64 res = 0;
    for (auto it = itl; it != itr; ++it)
        res = (res + qpow(it->val, x, y) * (it->r - it->l + 1)) % y;
    return res;
}

int n, m;
i64 seed, vmax;

i64 rnd() {
    i64 ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; i++)
        odt.insert({i, i, rnd() % vmax + 1});

    while (m--) {
        int op = rnd() % 4 + 1;
        int l  = rnd() % n + 1;
        int r  = rnd() % n + 1;
        if (l > r) swap(l, r);
        i64 x, y;
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else         x = rnd() % vmax + 1;
        if (op == 4) y = rnd() % vmax + 1;

        if (op == 1)      add(l, r, x);
        else if (op == 2) assign(l, r, x);
        else if (op == 3) cout << kth(l, r, x) << "\n";
        else              cout << sum_pow(l, r, x, y) << "\n";
    }
    return 0;
}

例题 2：CF 915E — Physical Education Lessons

【题意】

有 nn 个工作日，初始全部为工作日。qq 次操作，每次操作将区间 [l,r][l, r] 全部设为工作日 k=1k=1 或非工作日 k=2k=2。每次操作后输出当前工作日总数。

n≤109n \le 10^9，q≤3×105q \le 3\times 10^5。

【分析】

nn 极大，无法直接维护数组。但操作次数 qq 相对较小，大量连续区间值相同——ODT 天然适用。

关键： 全是区间赋值操作，没有区间加，ODT 区间数保持在 O(q)O(q) 级别。即使没有"随机数据"条件，纯赋值也足够高效。

int n, q, ans;

void assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it)
        ans -= (it->val == 1) * (it->r - it->l + 1);  // 减去旧值
    odt.erase(itl, itr);
    odt.insert({l, r, val});
    if (val == 1) ans += r - l + 1;  // 加上新值
}

例题 3：洛谷 P2787 — 语文1（chin1）- 理理思维

【题意】

维护一个字符串，支持三种操作：

  1. 区间赋值（全部改为同一字母，大写/小写）
  2. 区间查询某字母出现次数
  3. 区间排序（按字母表顺序重排）

n,m≤5×104n, m \le 5\times 10^4。

【思路】

存 26 棵 ODT / 或用 ODT 存字符。区间排序本质是：

  1. 统计区间内各字母出现次数
  2. 对区间连续赋值（按 A~Z 依次填回）

由于字符集只有 26，一次排序使区间数不超过 26，ODT 高效。

例题 4：洛谷 P2572 — [SCOI2010] 序列操作

【题意】

长度为 nn 的 01 序列，支持五种操作：

  1. 区间赋值为 0
  2. 区间赋值为 1
  3. 区间取反（0→1，1→0）
  4. 区间求和（1 的个数）
  5. 区间最长连续 1 的长度

n,m≤105n, m \le 10^5。

【思路】

线段树经典题，但 ODT 也能做。由于全是 01 操作，区间数收敛很快。取反操作需遍历每个值段逐个翻转。

例题 5：洛谷 P5350 — 序列

【题意】

维护序列，支持：区间求和、区间赋值、区间加、区间复制、区间交换、区间翻转。n,m≤3×105n, m \le 3\times 10^5。

【思路】

ODT + 可持久化平衡树（如 FHQ Treap）配合使用。区间复制/交换/翻转需要更强大的平衡树，但 ODT 的分块思想仍然是基础。

七、练习题推荐

题目 来源 难度
CF 896C Codeforces ★★★
CF 915E ★★☆
洛谷 P2787 洛谷
洛谷 P2572 SCOI 2010 ★★★
洛谷 P5350 洛谷 ★★★★
洛谷 P4979 矿洞：坍塌 ★★★
洛谷 P2894 Hotel ★★☆
洛谷 P3740 贴海报
CF 1638E Colorful Operations ★★★★

八、常见坑与技巧

  1. 必须 split(r+1) 再 split(l)：因为先 split(l) 可能使后面的迭代器失效。
  2. mutable 关键字：set 中的元素是 const 的，修改 val 需要 mutable。
  3. lower_bound 陷阱：不能直接用 set::lower_bound，应使用自定义比较——但此处直接用全局 lower_bound 配合 Node{pos, 0, 0} 也可。
  4. ODT 不是银弹：如果题目没有区间赋值，或者有构造数据，直接用线段树/平衡树。
  5. 区间数爆炸：当只有区间加而无赋值时，区间数 =n= n，ODT 退化为暴力。
  6. Hack ODT：构造交替赋值 + 加法的序列可使 ODT 退化。CF 896C 因数据随机所以安全。

九、总结

珂朵莉树的核心就一句话：用 set 维护等值区间，靠区间赋值操作压缩区间数，从而在随机数据下达到近似 O(mlog⁡n)O(m\log n) 的效率。

  • 优点：代码短、思路直观、适用于各种"暴力美学"场景
  • 缺点：可被卡到 O(nm)O(nm)，必须谨慎评估数据特征
  • 适用：有 assign 操作 + 随机/非卡 ODT 的数据

讲稿编写于 2026-05-24


我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2024054233号
  3. Worker 0, 19ms
  4. Powered by Hydro v5.0.1 Community, Modified by 33DAI