珂朵莉树(Chtholly Tree/ODT)学习笔记

发布于 2021-08-04  129 次阅读


参考:泥土笨笨的博客,Leap_Frog 的博客

好久没写学习笔记了啊……

珂朵莉树

模板:CF896C Willem, Chtholly and Seniorious

题意:

  • 给定一个序列,支持区间加,区间赋值,询问区间第 $k$ 小,区间幂次和(即 $x$ 次方的和,取模)。
  • 数据范围 $10^5$,数据随机。

珂朵莉树(Chtholly Tree),又称 ODT(Old Driver Tree),是一种暴力数据结构,其复杂度正确一般仅限于:存在区间赋值操作(常称为区间推平,即将一个区间的数变为同一个)且数据随机。

基本结构

珂朵莉树用将整个序列分为若干个区间,用 $l,r,v$ 来记录一个值均为 $v$ 的区间 $[l,r]$。

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 &a)const{
        return l<a.l;//按左端点排序存放在 set 中
    }
};
set<node> s;

我们将这些区间存放在一个 set 中,由于该 set 中的某个元素的 $v$ 可能会被修改,因此 mutable 必不可少。

刚开始时 set 中为 $n$ 个长度为 $1$ 的段。

分裂操作 split

分裂操作是珂朵莉树的核心,对于一个区间 $[l,r]$,我们给定一个值 $pos$,需要将其拆分为 $[l,pos-1]$ 和 $[pos,r]$ 两个区间。

本文中我直接使用了 auto,但如果在较低的 c++ 版本(如 c++98),需要将 auto 改为 set<node>::iterator

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

对于分裂操作,我们先找到 $pos$ 对应的区间。使用 lower_bound 找到一个区间后,若该区间的开头即为 $pos$,那么无需分裂,直接返回。反之,$it$ 往前一个位置就是 $pos$ 所在的区间。同时,若 $pos=n+1$(该情况见后文),我们判断一下返回即可(即第三行)。

接着,我们只需要将原来那个区间删除,并将两个新区间分别插入即可。

由于 insert 函数的返回的是一个 pair 且其 first 就为迭代器,我们可以直接如最后一行一样返回 $pos$ 所在区间的迭代器。

推平操作 assign

随机的推平操作是保证复杂度的关键。

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

我们只需要找到 $l$ 和 $r+1$ 所在的区间,将之间的区间全部删除,插入一个新区间即可。

在数据随机时,随机的 assign 操作能够使区间数趋近于 $\log n$ 并保持稳定,因此复杂度为 $O(m\log n)$。

详细证明见 Blaze 的博客

其他操作

区间加 add

inline void add(int l,int r,int k){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++) it->v+=k;
}

找到两端所在区间,暴力加即可。

区间第 $k$ 小

inline int getrank(int l,int r,int k){
    vector<pair<int,int>> vec;//vec.clear();
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++)
        vec.push_back(mk(it->v,it->r-it->l+1));
    sort(vec.begin(),vec.end());
    for(auto it=vec.begin();it!=vec.end();it++){
        k-=it->second;
        if(k<=0) return it->first;
    }
    return 114514;
}

用 vector 把所有区间排一下序,暴力找即可。

区间幂次和

inline int getpow(int l,int r,int k,int p){
    auto itr=split(r+1),itl=split(l);
    int ret=0;
    for(auto it=itl;it!=itr;it++)
        ret=(ret+(it->r-it->l+1)%p*ksm(it->v,k,p)%p)%p;//ksm 为快速幂
    return ret;
}

同理。

容易发现除了 split,其他操作都是极其暴力的,复杂度全靠随机的 assign 来保证。因此,珂朵莉树的使用范围还是比较狭窄的。

一道例题

CF453E Little Pony and Lord Tirek

题意:

  • 你有 $n$ 只小马(编号从 $1$ 到 $n$)。每只小马有三种属性。
  • $s_i$:时间为 $0$ 时这只小马拥有的法力值。
  • $m_i$:这只小马可以拥有的最大法力值。
  • $k_i$:这只小马单位时间内回复的法力值。
  • 提雷克会给出 $m$ 条指令,每一条都可以被描述为 $3$ 个整数:$t_i, l_i, r_i$。表示在时间为 $t_i$ 时,提雷克会从区间 $[l_i,r_i]$ 的小马中吸取其所有法力,指令保证 $t$ 升序,计算每一条指令之后提雷克可以吸取多少点法力。

首先考虑一个子问题。若每次操作都针对整个序列且所有小马初始法力为 $0$,我们可以对于所有小马对于 $\frac{m_i}{k_i}$ 从小到大排序,我们发现对于每个时间,一定有一个前缀的答案为 $\sum m_i$,后缀的答案为 $\sum k_i \times \Delta t$($\Delta t$ 为时间差)。

再回到这个问题,我们发现其所有操作都为推平操作(吸走所有魔力),那么我们考虑对于一个区间 $[l,r]$,该区间内所有小马都在 $v$ 时间法力值归零,并一直增长到当前时间的,发现这种区间可以用珂朵莉树维护,并且可以用上述方法计算贡献。具体的,我们将所有小马排序后一头一头加入主席树中(已加入的小马对于答案的贡献为 $m_i$,还没加入的贡献为 $k_i\times \Delta t$),然后对于一个区间,我们计算出其与询问时间的时间差,再二分找到该时间差对应哪一时刻的主席树,然后查询该区间的贡献即可。由于问题中仅存在推平操作,复杂度一定是正确的。

如果对于代码或具体实现有疑惑,可以查看文章开头给出的 Leap_Frog 的博客链接。

完整代码(CF896C)

#include<bits/stdc++.h>
#define IT set<node>::iterator
#define int long long
#define mk make_pair
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n,m,seed,vmax;
inline int rnd(){
    int ret=seed;
    seed=(seed*7+13)%mod;
    return ret;
}
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 &a)const{
        return l<a.l;
    }
};
set<node> s;
auto split(int pos){
    auto it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) return it;
    it--;if(it->r<pos) return s.end();
    int l=it->l,r=it->r,v=it->v;
    s.erase(it);
    s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).first;
}
inline void add(int l,int r,int k){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++) it->v+=k;
}
inline void assign(int l,int r,int k){
    auto itr=split(r+1),itl=split(l);
    s.erase(itl,itr);s.insert(node(l,r,k));
}
inline int getrank(int l,int r,int k){
    vector<pair<int,int>> vec;//vec.clear();
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;it++)
        vec.push_back(mk(it->v,it->r-it->l+1));
    sort(vec.begin(),vec.end());
    for(auto it=vec.begin();it!=vec.end();it++){
        k-=it->second;
        if(k<=0) return it->first;
    }
    return 114514;
}
inline int ksm(int a,int b,int p){
    a%=p;
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ret;
}
inline int getpow(int l,int r,int k,int p){
    auto itr=split(r+1),itl=split(l);
    int ret=0;
    for(auto it=itl;it!=itr;it++)
        ret=(ret+(it->r-it->l+1)%p*ksm(it->v,k,p)%p)%p;
    return ret;
}
int a[N];
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        s.insert(node(i,i,a[i]));
    }
    for(int i=1,op,l,r,x,y;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;
        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) printf("%lld\n",getrank(l,r,x));
        else printf("%lld\n",getpow(l,r,x,y));
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣