珂朵莉树（ODT）入门

_7Mr · 2023-12-06 14:36:28 · 个人记录

0xFF 前言

若不熟悉 STL 中的 set，请熟练后，再看本文章，珂朵莉树大多数写法都是是基于 set 实现的。（不熟练也可以看简介，但接下来的理解可能有点困难）

谨记，珂朵莉是全世界最幸福的女孩。

0x00 set 简介

insert(x) 当容器中没有等价元素的时候，将元素 x 插入到 set 中。
erase(l,r) 删除迭代器在 [l,r) 范围内的所有元素。
set 的遍历。

for(set<node>::iterator it=s.begin();it!=s.end();it++)

0x01 引入

当我们遇到一道数据结构题，又不想打正解的时候，珂朵莉树上场了。珂朵莉树（Chtholly Tree），又名老司机树 ODT（Old Driver Tree）,起源于 CF896C。注意，这种想法的本质是基于数据随机的颜色段均摊，而不是一种数据结构。

请注意，使用珂朵莉树通过的所有题目均是因为数据水通过的，珂朵莉并非正解（除非出题人想考珂朵莉树），珂朵莉树可以被精心构造的数据卡到超时。

0x02 珂朵莉树的时间复杂度

在数据纯随机的情况下，珂朵莉树使用 set 的时间复杂度为 O(n \log \log n)，更准确的时间复杂度证明请见珂朵莉树的复杂度分析。

0x03 珂朵莉树的保存数据

珂朵莉树有 3 个重要值，l、r、val，具体什么意思，我们来看下面的一串数列。

\color{red}\text{111}\color{blue}\text{33}\color{orange}\text{2}\color{green}\text{44}

在珂朵莉树里，他们就会被保存为 \color{red}[1,3,1]、\color{blue}[4,5,3]、\color{orange}[6,6,2]、\color{green}[7,8,4]。相信聪明的读者已经发现 l 代表一段元素相同的区间内的左端点，r 代表一段元素相同的区间内的右端点，val 代表一段元素相同的区间内的元素值。

以此我们就可以写出珂朵莉树保存数值的代码。

struct node {
    int l,r;//左右端点
    mutable int v;//数值
    node(int L,int R=0,int V=0) : l(L),r(R),v(V) {}
    bool operator < (const node &x) const {//按左端点进行排序
        return l<x.l;
    }
};

注：mutable 的意思是可变的，让我们可以在后面的操作中修改 v 的值。在 C++ 中，mutable 是为了突破 const 的限制而设置的。被 mutable 修饰的变量（mutable 只能用于修饰类中的非静态数据成员），将永远处于可变的状态，即使在一个 const 函数中。

这意味着，我们可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set。——oi-wiki。

总而言之，珂朵莉树就是把值相同的区间合并成一个结点保存在 set 里面。

0x04 珂朵莉树分裂操作

这个操作是珂朵莉树最重要的操作之一，它就是将一个集合拆成两部分，有一部分需要修改，而另一部分不需要修改，要修改的就分裂开进行修改，不修改的就分裂开不管它。

set<node>::iterator spilit(int pos) {
    set<node>::iterator it=ODT.lower_bound(node(pos)); // 找到第一个不小于 pos 的节点
    if(it!=ODT.end() && it->l==pos) return it; //如果 pos 是某个节点的左端点，直接返回该节点。
    it--;
    if(it->r<pos) return ODT.end();//pos 在前一个区间中。
    int V=it->v,L=it->l,R=it->r;//把值取出来
    ODT.erase(it);//删除
    ODT.insert(node(L,pos-1,V))//插入;
    return ODT.insert(node(pos,R,V)).first;//返回
}

0x05 珂朵莉树推平操作

单独只有分裂操作珂朵莉树的时间复杂度飙上天，有了推平操作，珂朵莉树的时间复杂度就会变得稳定，换一种讲法推平操作是珂朵莉树不可或缺的操作，所谓推平操作，就是指，将一段区间内的数全部修改为一个值。

void bulldoze(int l,int r,int x) {
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);//分裂
    ODT.erase(itl,itr);//删除原来的区间
    ODT.insert(node(l,r,x));//将我们要推平的区间加进去
}

请注意：我们在珂朵莉树内分裂求区间左右端点操作时，必须先 split 右端点，再 split 左端点。若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，因此导致 RE，下面都遵循此规则。

0x06 珂朵莉树区间加

和推平操作大差不差，将每个数拉出来加一下就行了。

void add(int l,int r,int x) {
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);//分裂
    for(; itl!=itr; itl++) itl->v+=x;//单独拉出来加
}

0x07 珂朵莉树的其他操作

对于珂朵莉树的其他操作，只需要分裂完后，将每一个单独拉出来做一下操作就好了。~~简单来说就是套板子。~~

void hanshuming(int l,int r,int x) {
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);
    for(; itl!=itr; itl++) {
        //(进行操作)
    }
}

0x08 珂朵莉树实战

我们以珂朵莉树模板题CF896C为例。

题面

1 l r x：将 [l,r] 区间所有数加上 x。

2 l r x：将 [l,r] 区间所有数改成 x。

3 l r x：输出将 [l,r] 区间从小到大排序后的第 x 个数是的多少(即区间第 x 小，数字大小相同算多次，保证 1 \le x \le r-l+1。

4 l r x y：输出 [l,r] 区间每个数字的 x 次方的和模 y 的值(即((\sum^r_{i=l}a_i^x) \bmod y)。

对于操作 1，珂朵莉基本操作，上讲过不过多赘述。
对于操作 2，珂朵莉基本操作，上讲过不过多赘述。
对于操作 3，把元素挨个取出，暴力进行排序，查找第 x 小。
对于操作 4，反正就是暴力，直接暴力找元素，然后快速幂。

注意不要忘记区间总个数。像这种珂朵莉树的题，反正就是分裂完之后暴力解就行了。

#include<bits/stdc++.h>
#define int long long
#define double long double
#define INF INT_MAX
using namespace std;
const int maxn=1e5+5,mod=1e9+7;
int n,m,seed,vmax;
int a[maxn];
struct node {//定义
    int l,r;
    mutable int v;
    node(int L,int R=-1,int V=0) : l(L),r(R),v(V) {}
    bool operator < (const node &x) const {
        return l<x.l;
    }
};
set<node> ODT;
set<node>::iterator spilit(int pos) {//分裂
    set<node>::iterator it=ODT.lower_bound(node(pos,-1,0));
    if(it!=ODT.end() && it->l==pos) return it;
    it--;
    if(it->r<pos) return ODT.end();
    int V=it->v,L=it->l,R=it->r;
    ODT.erase(it);
    ODT.insert(node(L,pos-1,V));
    return ODT.insert(node(pos,R,V)).first;
}
void bulldoze(int l,int r,int x) {//推平
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);
    ODT.erase(itl,itr);
    ODT.insert(node(l,r,x));
}
void add(int l,int r,int x) {//区间加
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);
    for(; itl!=itr; itl++) itl->v+=x;
}
int ksmall(int l,int r,int x) {//暴力就对了
    vector<pair<int,int> > h;
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);
    for(; itl!=itr; itl++) h.push_back(pair<int,int>(itl->v,itl->r-itl->l+1));//取出来
    sort(h.begin(),h.end());//排个序
    for(vector<pair<int,int> >::iterator it=h.begin(); it!=h.end(); it++) {
        x-=it->second;
        if(x<=0) return it->first;//暴力找
    }
}
int ksm(int a,int b,int p) {//快速幂
    int res=1;
    a%=p;//本题特殊，有可能会超
    while(b) {
        if(b%2) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
int section(int l,int r,int sum,int p){//暴力
    set<node>::iterator itr=spilit(r+1),itl=spilit(l);
    int res=0;
    for(;itl!=itr;itl++) res=(res+(itl->r-itl->l+1)*ksm(itl->v,sum,p)%p)%p;//直接暴力
    return res;
}
int rnd() {//按照题目要求
    int ret;
    ret=seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>seed>>vmax;
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        ODT.insert(node(i,i,a[i]));//加入节点
    }
    ODT.insert(node(n+1,n+1,0));
    for(int i=1;i<=m;i++){
        int op=(rnd()%4)+1;//按照题目要求
        int l=(rnd()%n)+1;
        int r=(rnd()%n)+1;
        int x=0,y=0;
        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;
        if(op==1) add(l,r,x);
        if(op==2) bulldoze(l,r,x);
        if(op==3) cout<<ksmall(l,r,x)<<endl;
        if(op==4) cout<<section(l,r,x,y)<<endl;
    }
    return 0;
}

0x09 总结

反正就是除了分裂，其他分裂出来（~~套板子~~），暴力就行了。

这里提供一道我自己出的珂朵莉树的题目，难度大体是蓝，挺简单的。

练习提单,持续不断更新

完结，撒花✿✿ヽ(°▽°)ノ✿。