珂朵莉树（Chtholly Tree/ODT）学习笔记

参考：泥土笨笨的博客，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;
}