珂朵莉树

yuanzhiteng · 2023-09-26 22:44:16 · 个人记录

参考资料

一. 什么是珂朵莉树

珂朵莉树（Chtholly\ Tree），又名老司机树 ODT（Old\ Driver \ Tree），起源于 这道题。

本质上是一种基于随机数据的颜色段均摊，是一种想法，一种优雅的暴力，而非一种特殊的数据结构。

用于 随机数据下 含区间赋值操作 的数据结构题。

在随机数据下时间复杂度是均摊的 \mathcal{O}(n\log \log n)，而当数据不随机时会被精心构造的数据卡 T。

二. 珂朵莉树的实现

主要思想是对每一段（值相同的一段区间）合并成一个节点保存在 set 里面，修改时将需要的段分裂出来再合并，暴力统计答案，暴力修改。

比如序列长这样：

将值相同的每一段看作是一个区间。

初始化

我们这样来保存节点：

struct node{                                                //node存放每一连续段
    int l,r;                                                //l,r:这一连续段的左右端点,val:这一连续段的值
    mutable ll val;                                         //用mutable是使得后面的常量迭代器能够修改val

    bool operator < (const node &x)const{                   //按照左端点排序
        return l < x.l;
    }
};
set<node>s;

注释很详细了。

需要注意的是这里的 val 类型声明要有 mutable，否则会 CE，至于为什么后面修改操作中会说。

存储后长这样：

刚开始时将每一个 [i,i] 视为一个区间插入 set 中即可。

核心操作 split

用于将一个区间 [l,r] 从 pos 处分割成两个区间 [l,pos-1],[pos,r]。

注意不是 [l,pos],[pos+1,r]。

#define iter set<node>::iterator

iter split(int pos){                                    //将含pos的连续段[l,r]分成[l,pos-1],[pos,r]两段,并返回[pos,r]的迭代器
    iter it = s.lower_bound((node){pos,0,0});
    if(it != s.end() && it->l == pos)                   //pos为区间[l,r]的开头(pos==l),不用split,直接返回这个区间的迭代器
        return it;
    it--;                                               //it--后就是包含了pos的区间
    if(it->r < pos)                                     //pos超出了整个s的范围,直接返回s.end()
        return s.end();
    int l = it->l,r = it->r;
    ll val = it->val;
    s.erase(it);                                        //删除原区间
    s.insert((node){l,pos-1,val});                      //加入左区间
    return s.insert((node){pos,r,val}).first;           //加入右区间(返回值是一个pair,其first正好是该区间的迭代器)
}

需要找到 pos 所在的区间对应 set 中的点。

分三种情况：pos 超出整个 s 的范围，pos 恰好是一个区间的开头，pos 再区间中。

对于第一种情况，直接返回 s.end() 即可。

对于第二种情况，直接返回当前区间的迭代器即可。

对于第三种情况，将原先区间 erase 掉，再插入分裂后的两个区间并返回 [pos,r] 的迭代器即可。

代码注释也很详细了。

推平操作 assign

保证珂朵莉树时间复杂度的关键。

用于区间赋值，同时可以将颜色段数变少。

比如要将 [2,8] 的元素全部变成 666，如下：

首先我们发现，[8,10] 是一个区间，那么需要先 split(9)，把 [8,8] 和 [9,10] 拆成两个区间。同理，原来的 [1,2] 区间，也需要拆成 [1,1]和 [2,2]。

接下来，我们把要被合并的从 2 到 8 的所有 node 都从 set 里面删掉，再重新插入一个 [2,8] 区间就行了。

删除某个范围内的元素可以用 set 的 erase 函数，这个函数接受两个迭代器 s和 t，把 [s,t) 范围内的东西都删掉。

inline void assign(int l,int r,ll x){                   //推平操作,将[l,r]统一赋值成x
    iter itr = split(r + 1),itl = split(l);             //注意:一定要先split(r+1)再split(l)!!!否则可能l的迭代器已经被释放掉导致RE!!!
    s.erase(itl,itr);                                   //删除原区间.erase的是[itl,itr),所以上面才split(r+1)
    s.insert((node){l,r,x});                            //插入新区间
}

尤其需要注意的是：

一定要先 split(r+1) 再 split(l)！！！

不然的话可能会因为 l 已经被 erase 掉而 RE。

例子：从区间 [1,4] 中截取 [1,1] 出来，然后你就能发现为什么了。

后面但凡涉及 split(r+1),split(l) 的都要遵循此原则。

修改操作 add

暴力将需要修改的区间截取出来均修改即可。

inline void add(int l,int r,ll x){                      //[l,r]统一加上x
    iter itr = split(r + 1),itl = split(l);
    for(iter it=itl;it!=itr;it++)                       //暴力修改即可
        it->val += x;
}

这里也解释了为什么之前 val 要声明为 mutable。

如果不声明，这里的 it->val+=x 会报错，因为 it 是个常量迭代器，无法修改对应的 val。但是提前声明成 mutable 就可以修改了。

查询操作

都是暴力 \cdots\cdots

比如在模板题中，查询区间第 k 小操作，直接将对应的区间取出来排序，从小到大看够不够即可。

struct Rank{                                            //题目要求的查排名
    ll val;
    int cnt;

    bool operator < (const Rank &x)const{
        return val < x.val;
    }
};
inline ll kth(int l,int r,int k){                       //查询区间第k小
    iter itr = split(r + 1),itl = split(l);
    vector<Rank>v;
    for(iter it=itl;it!=itr;it++)                       //暴力插入
        v.emplace_back((Rank){it->val,it->r - it->l + 1});
    sort(v.begin(),v.end());                            //暴力排序
    for(auto x:v)                                       //暴力找第k小
        if(x.cnt < k)   k -= x.cnt;
        else return x.val;
    return -1;
}

再比如模板题中的区间 x 次方和操作，也是直接取出对应区间暴力统计答案：

inline ll calc(int l,int r,ll x,ll mod){                //题目要求的求[l,r]每个数的x次方和%mod
    iter itr = split(r + 1),itl = split(l);
    ll ret = 0;
    for(iter it=itl;it!=itr;it++)                       //暴力求
        ret = (ret + quickpow(it->val,x,mod) * (it->r - it->l + 1ll) % mod) % mod;
    return ret;
}

其他的就没什么了，查询方面要是具体题目而定，在珂朵莉树的加成下基本都是暴力搞。

模板题 代码如下：

/*知识点:珂朵莉树*/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
#include <vector>
#define iter set<node>::iterator
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

template <typename T>
inline void read(T& x){
x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c=getchar();}
while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48),c = getchar(); } x *= f;
}
template <typename T,typename... Args>
inline void read(T &x, Args&... Arg){read(x),read(Arg...); }

inline ll quickpow(ll x,ll k,ll mod){
    x %= mod;                                               //注意k不能一来就取模,不然会WA
    ll ret = 1;
    while(k){
        if(k & 1)   ret = ret * x % mod;
        x = x * x % mod;
        k >>= 1;
    }
    return ret;
}

struct node{                                                //node存放每一连续段
    int l,r;                                                //l,r:这一连续段的左右端点,val:这一连续段的值
    mutable ll val;                                         //用mutable是使得后面的常量迭代器能够修改val

    bool operator < (const node &x)const{                   //按照左端点排序
        return l < x.l;
    }
};
set<node>s;

struct Chtholly_Tree{                                       //珂朵莉树

    iter split(int pos){                                    //将含pos的连续段[l,r]分成[l,pos-1],[pos,r]两段,并返回[pos,r]的迭代器
        iter it = s.lower_bound((node){pos,0,0});
        if(it != s.end() && it->l == pos)                   //pos为区间[l,r]的开头(pos==l),不用split,直接返回这个区间的迭代器
            return it;
        it--;                                               //it--后就是包含了pos的区间
        if(it->r < pos)                                     //pos超出了整个s的范围,直接返回s.end()
            return s.end();
        int l = it->l,r = it->r;
        ll val = it->val;
        s.erase(it);                                        //删除原区间
        s.insert((node){l,pos-1,val});                      //加入左区间
        return s.insert((node){pos,r,val}).first;           //加入右区间(返回值是一个pair,其first正好是该区间的迭代器)
    }

    inline void assign(int l,int r,ll x){                   //推平操作,将[l,r]统一赋值成x
        iter itr = split(r + 1),itl = split(l);             //注意:一定要先split(r+1)再split(l)!!!否则可能l的迭代器已经被释放掉导致RE!!!
        s.erase(itl,itr);                                   //删除原区间.erase的是[itl,itr),所以上面才split(r+1)
        s.insert((node){l,r,x});                            //插入新区间
    }

    inline void add(int l,int r,ll x){                      //[l,r]统一加上x
        iter itr = split(r + 1),itl = split(l);
        for(iter it=itl;it!=itr;it++)                       //暴力修改即可
            it->val += x;
    }

    struct Rank{                                            //题目要求的查排名
        ll val;
        int cnt;

        bool operator < (const Rank &x)const{
            return val < x.val;
        }
    };
    inline ll kth(int l,int r,int k){                       //查询区间第k小
        iter itr = split(r + 1),itl = split(l);
        vector<Rank>v;
        for(iter it=itl;it!=itr;it++)                       //暴力插入
            v.emplace_back((Rank){it->val,it->r - it->l + 1});
        sort(v.begin(),v.end());                            //暴力排序
        for(auto x:v)                                       //暴力找第k小
            if(x.cnt < k)   k -= x.cnt;
            else return x.val;
        return -1;
    }

    inline ll calc(int l,int r,ll x,ll mod){                //题目要求的求[l,r]每个数的x次方和%mod
        iter itr = split(r + 1),itl = split(l);
        ll ret = 0;
        for(iter it=itl;it!=itr;it++)                       //暴力求
            ret = (ret + quickpow(it->val,x,mod) * (it->r - it->l + 1ll) % mod) % mod;
        return ret;
    }
}ODT;

int n,m;
ll seed,vmax;
inline ll rnd(){                                            //下面的都是这道题特殊的读入数据了,跟Chtholly Tree无关
    ll ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}
int main(){

    read(n,m,seed,vmax);
    for(int i=1;i<=n;i++){
        ll a = (rnd() % vmax) + 1;
        s.insert((node){i,i,a});
    }
    while(m--){
        int op = (rnd() % 4) + 1;
        int l = (rnd() % n) + 1;
        int r = (rnd() % n) + 1;
        if(l > r)   swap(l,r);
        ll x = 0,y = 0;
        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
            ODT.add(l,r,x);
        else if(op == 2)                                    //assign
            ODT.assign(l,r,x);
        else if(op == 3)                                    //kth
            printf("%lld\n",ODT.kth(l,r,x));
        else                                                //calc
            printf("%lld\n",ODT.calc(l,r,x,y));
    }

    return 0;
}

三. 珂朵莉树的应用

Willem, Chtholly and Seniorious

珂朵莉树的起源。

就是上面的例题。

练板子用。

代码上面有。

Physical Education Lessons

很简单的一道珂朵莉树的应用。

题目并没有保证数据随机。

然鹅，珂朵莉树并不会被卡。

因为想要卡珂朵莉树就要卡 assign，要让 assign 也就是区间赋值尽可能地少。

但是这道题的修改操作本就全是赋值操作。

需要注意的是，不能每次都暴力查询，会 T。

应该开一个全局答案 ans，每次 assign 时顺便更新答案即可。

code

Water Tree

是的，珂朵莉树还可以在某些题目中直接取代线段树。

比如这道题。

全是区间赋值操作怎么不用既可爱又好码的珂朵莉树呢？

树上问题再写个树剖即可。

刚开始树剖甚至写挂了。

code

[LnOI2019] 第二代图灵机

一道将珂朵莉树与其它数据结构结合的好题。

我们仔细观察题目，发现颜色和数字不相关，可以分开维护。

颜色：

题目明确说了是随机数据，并且颜色还有区间赋值的推平操作。

强烈暗示我们用珂朵莉树维护颜色段。

事实也确实如此，直接维护即可。

数字：

要维护区间最大值，区间最小值，以及区间和。

维护区间和的原因显然，查询就是这个。

至于为什么要维护区间最大值和区间最小值，下面会讲。

查询：

对于查询 1：

不难想到在珂朵莉树上使用双指针（尺取法）。

每次将 it 右移一格，判断此时出现的颜色总数是否为 c（类似于莫队）。

当颜色总数为 c 时，不断右移 itl 缩小合法区间更新答案。

注意线段树上应该查询 [itl\to r,it\to l] 这段的区间和。

正确性显然，这样可以使区间在合法的情况下尽可能地小。

应当注意的是当 c=1 时，要特判，答案为 [1,n] 的最小值。

对于查询 2：

跟 1 差不多，只不过每次是将 it 右移一格。

然后不断右移 itl 直到 cnt[it\to val]=1，并更新答案。

查询也一样，线段树上查询 [itl\to r,it\to l] 的区间和。

这样能保证每种颜色至多只出现一次，并且区间和最大。

有几个细节：

当 it 处颜色段的长度不为 1 即 it\to l \neq it\to r，那么在当前答案已经更新后，这段就一定不合法了，要将 itl 移到 it 的位置，it++，这样便跳过了这段区间。

其次，答案 ret 的初始值应该赋为 [1,n] 的区间最大值，因为 1 个数字一定合法，并且这是最坏情况，这样便能保证同一个颜色段内的不会被漏算。

所以线段树才要维护区间最大值和区间最小值。

代码实现还是不难的。

时间复杂度上，由于珂朵莉树保证了颜色段均摊，双指针均摊意义下只会移动 \mathcal{O}(log\ n) 次，每次线段树上查询是 \mathcal{O}(log\ n) 的。

因此总时间复杂度为 \mathcal{O}(m\log ^2 n)。

实测代码吸氧 902ms，跑得飞快。

code

[Ynoi Easy Round 2021] TEST_152