珂朵莉树/老司机树学习笔记

c_legg · 2025-02-15 23:13:19 · 算法·理论

前言

\gets 锦标赛排序学习笔记 - 洛谷专栏

好难受啊，我好菜啊，完全不知道要干什么，就写了这篇专栏放放松。

介绍

珂朵莉树（Chtholly Tree）也叫老司机树（ODT），是一种基于平衡树（一般用 set 或 map 实现）的暴力算法，可用于解决区间修改、区间加法、区间查询以及其他区间操作，在处理区间修改效率最高，适用于随机数据。

实现

从 P3740 [HAOI2014] 贴海报开始

虽然这题并不是经典的珂朵莉树题，但因为这题只需实现 split 和 assign 操作，比较简单，我就把它放到最前面好了。

题意大致是：给出一个区间 [1,n]，最初所有元素颜色均为 0，要进行 m 次操作，对于第 i 次操作，给出 a_i,b_i，把区间 [a_i,b_i] 中所有元素染成颜色 i，其中 i\in\mathbb N\cap[1,m]，求结束后的颜色个数。

可以用一些奇怪的办法做，比如线段树+离散化，浮水法之类的（我没写过不知道），但这不重要，我们开始讲珂朵莉树。

珂朵莉树本质上就是维护若干个区间，每个区间中的所有值都相等，相邻区间中的值可以相等。我们用一个结构体来表示一个区间：

struct node {
    int l, r;
    mutable int val; // 让 val 保持可变状态

    node(int a, int b=-1, int c=0) { // 构造函数
        l=a, r=b, val=c;
    }
    bool operator<(const node &oth)const { // 比较函数，后面会用
        return l<oth.l;
    }
};

然后我们有一堆 node 即区间，把他们用 set 排成一排：

set<node> cht; // 珂朵莉树 Chtholly Tree

然后我们要进行区间赋值，但如果区间赋值的边缘与当前区间的边缘不一致就比较困难，这个时候我们可以考虑把目前的区间分割一下再处理。

比如原本的区间像下面这样：

而下图中蓝色部分是我们要修改的区间：

然后我们把第 3、5 个区间沿红线切割，并删掉中间所有区间，再创建一个区间，值为 666：

现在事情就好办了，我们要写 2 个函数，分别负则切割和赋值：

auto split(int pos) { // 分割成 [l, pos) [pos, r]  返回[pos, r]
    auto it=cht.lower_bound(node(pos)); // 找到第一个区间 [l,r] 使得 l>=pos
    if(it!=cht.end() && it->l==pos) return it; // 不用分割
    it--; // 到左边去 此时 l<=pos<r
    int l=it->l, r=it->r, val=it->val;
    cht.erase(it); // 删掉此区间
    cht.insert(node(l, pos-1, val)); // 插入左区间
    return cht.insert(node(pos, r, val)).first; // 插入并返回右区间
}

inline void assign(int l, int r, int v) { // 赋值 把 [l, r] 中所有值改成 val
    auto itr=split(r+1), itl=split(l); // 分割 这里分 r+1 是因为 erase 删除的是一个左闭右开区间
    cht.erase(itl, itr);
    cht.insert(node(l, r, v)); // 插入新节点
}

接着让我们回到上面那题，就可以发现这是一道裸的珂朵莉树题，修改上面已经讲过了，求最终答案时，只要遍历 set，再用一个 unordered_set 对颜色去重即可：

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

int n, m;

struct node {
    int l, r;
    mutable int val;

    node(int a, int b=-1, int c=0) {
        l=a, r=b, val=c;
    }
    bool operator<(const node &oth)const {
        return l<oth.l;
    }
};

set<node> cht;

auto split(int pos) {
    auto it=cht.lower_bound(node(pos));
    if(it!=cht.end() && it->l==pos) return it;
    it--;
    int l=it->l, r=it->r, val=it->val;
    cht.erase(it);
    cht.insert(node(l, pos-1, val));
    return cht.insert(node(pos, r, val)).first;
}

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

unordered_set<int> ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>m;
    cht.insert(node(1, n));
    for(int i=1; i<=m; i++) {
        int l, r;
        cin>>l>>r;
        assign(l, r, i);
    }
    for(auto i : cht) {
        ans.insert(i.val);
    }
    cout<<ans.size()-ans.count(0);
    return 0;
}

简单练习一下（用珂朵莉树可能过不了，但却是是练习的好题）

P1840 Color the Axis
P4344 [SHOI2015] 脑洞治疗仪
P1558 色板游戏
P4979 矿洞：坍塌

再看模板题 CF896C Willem, Chtholly and Seniorious

其实把这题的随机函数去掉，就只是要我们维护区间加法、区间赋值、区间第 x 小，区间 x 次幂和模 y，十分简单，我们一个个来解决。

对了，在处理之前，为了方便，我们先定义

auto itr=split(r+1), itl=split(l);

再来进行处理。

区间加法

很简单，把 itl 到 itr 中的每个区间的值都加上 x 即可。

for(; itl!=itr; itl++) itl->val+=x;

区间赋值

直接调用 assign。

cht.erase(itl, itr);
cht.insert(node(l, r, x));

区间第 x 小

我认为这个操作十分良好地体现了珂朵莉树“暴力”的特点，我们把 itl 到 itr 中的每个区间按其值排序，然后遍历找第 x 个就可以。

vector<pair<ll, ll> > arr; // 定义一个数组 first 为区间值 second 为区间长度
arr.clear(); // 清空
for(; itl!=itr; itl++) {
    ll v=itl->val;
    arr.push_back({v, itl->r-itl->l+1}); // 加入到末尾
}
sort(arr.begin(), arr.end()); // 按值排序
for(auto i: arr) { // 遍历
    x-=i.second;
    if(x<=0) { // 找到了
        cout<<i.first<<"\n";
        break;
    }
}

区间 x 次幂和模 y

做法和操作 1 很类似，加上一个快速幂即可，此处不给出快速幂代码。

ll ans=0;
for(; itl!=itr; itl++) {
    ans=(ans+(itl->r-itl->l+1)*poww(itl->val%y, x, y))%y;
}
cout<<ans<<"\n";

\color{#00AA00}\texttt{Accepted}

再练习一下（纯珂朵莉树也可能过不了）

P2572 [SCOI2010] 序列操作
P8146 [JRKSJ R4] risrqnis

后记

就先写到这吧，我有点累了。

到这里大致上就把珂朵莉树的基本思想和实现讲完了，要是遇到珂朵莉树的题再做不出，就只有 3 种原因了：

惨遭 hack ~（我很讨厌 hack 珂朵莉树的行为，一来是珂朵莉太可爱了，二来是这样做显得珂朵莉树什么都干不了，三来是我不会线段树）~
模板打错
不够俄罗斯

话说我突然感觉珂朵莉好可爱啊 qwq。

参考文献（撒花）

珂朵莉树/颜色段均摊 - OI Wiki

珂朵莉树学习笔记 - 洛谷专栏

珂朵莉树的复杂度分析 - 知乎