珂朵莉树学习笔记-摩杜云开发者社区

珂朵莉树，又名老司机树（Old Driver Tree，ODT），是一种暴力数据结构，是由数据结构毒瘤、Ynoi 出题人 lxl 发明的一种对随机数据十分有效的暴力数据结构。这里使用 set 实现的珂朵莉树时间复杂度为 $O(n\log n\log n)$。

珂朵莉树主要应用于区间的“推平”操作，就是对一个区间内的所有值进行修改。当然不局限于单一的推平，可能还有其他操作，这时我们就需要用到珂朵莉树。

考虑一下，我们把几个区间推平之后，整个序列就会变成好几段有相同数的区间：

$5$	$5$	$42$	$42$	$42$	$42$	$2$	$3$	$3$	$3$

我们用一个结构体来表示每个数字相同的段：

struct node
{
    int l,r;//左右端点
    mutable int v;//区间值
    friend bool operator < (node a,node b)
    {
        return a.l<b.l;//按左端点排序
    }
};

这样处理过后我们把每一段区间插入到一个 set 中，set 根据我们重载的运算符排序，这样我们的序列就维护好了，set 里存储的东西如下：

$l=1\r=2\v=5$	$l=3\r=6\v=42$	$l=7\r=7\v=2$	$l=8\r=10\v=3$

开始时，我们每段只有一个数，set 里维护 $n$ 个长度为 $1$ 的区间。

到此，珂朵莉树的预处理就结束了，下面的关键是两个重要的操作：split 分裂操作、assign 推平操作和 add 修改操作。

分裂

随着不断地推平，有一些区间会被合并，有一些区间会被分裂，这时就要用到 split 操作。

对于 split 操作，我们传入一个参数 p（position），从 $p$ 进行切割，寻找包含 $p$ 的区间，将其分裂成 $[l,p-1]$ 和 $[p,r]$ 两部分，返回的是分裂后的区间 $[p,r]$。如果 $p$ 就是某一区间的开头，直接返回即可。在这里我们不得不用一种神奇的东西——迭代器 iterator。这里的 iterator 在 set 中使用，类似指针指向区间即 set 中的元素。当然我们也可以使用 auto，但是我不会😭。

我们用 set 中的 lower_bound 函数，可以返回大于等于参数的第一个元素的位置，它可以方便地让我们的 it 在 set 中获得定位。定位 it 之后，我们考虑以下几种情况：

如果我们找到了一个以 $p$ 开头的区间，那么直接返回指向这个区间的迭代器。如果我们找到的这个 it 指的区间比包含 $p$ 的区间左端点大一点点或者比最后一个区间的右端点还要大，我们先无脑把 it 左移一位即 --it（考虑一下为什么要这么操作，其实是因为 lower_bound 函数返回的迭代器位置是大于等于，如果返回的是大于位置那么必须回退），然后去看 it 的右端点。如果小于 $p$，说明 $p$ 太大了，返回 s.end() 迭代器即可。否则，现在的 it 区间一定包含了 $p$，所以我们要分裂这个区间，即删除原来的区间，添加两个新区间 $[l,p-1]$ 和 $[p,r]$。

一个代码实现小技巧：insert 函数返回的是一个结构体，具体怎么利用它压行见下：

（关于 -> 这个操作，是指向结构体内变量的指针）

set<node>::iterator split(int pos)
{
    set<node>::iterator it=s.lower_bound(node{pos,0,0});
    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);//清空当前set准备分裂
    s.insert(node{l,pos-1,v});
    return s.insert(node{pos,r,v}).first;
}

推平

推平操作 assign 和分裂操作 split 是相反的两个操作。对于 assign 操作，我们考虑把所有要推平的区间都给删除掉，用推平后的区间取而代之。

举个栗子，对于下面的区间 $[2,8]$ 的元素，我们考虑将其推平成 $520$。

$l=1\r=2\v=5$	$l=3\r=6\v=42$	$l=7\r=7\v=2$	$l=8\r=10\v=3$

我们发现 $[8,10]$ 是一个区间，所以我们要 split(9) 分裂该区间，同理 $[1,2]$ 区间也需要分裂成 $[1,1]$ 和 $[2,2]$，最后把 $[2,8]$ 内的所有区间都删除然后插入一个新区间即可。我们可以用 erase 函数，它支持接受两个迭代器 p1 和 p2，把 $[p_1,p_2)$ 内的东西都删掉。

这里强调一个点，一定要先 split(r+1) 后 split(l)，顺序不能变！为什么，考虑一种情况：对于区间 $[1,4]$，我们要截取 $[1,1]$，那么我们要依次调用 split(2) 和 split(1)。如果先调用了 split(1)，我们的 itl 指向的是区间 $[1,4]$，itr 指向的是区间 $[2,4]$，这时候我们就会惊奇地发现我们的 itl 区间被 erase 掉了，于是乎我们就 RE 了。

void assign(int l,int r,int x)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node{l,r,x});
}

修改

对于修改操作 add，我们先像推平一样分裂头尾区间，然后利用迭代器指针更新区间内的值即可。

void add(int l,int r,int x)
{
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl;it!=itr;it++) it->v+=x;
}

其他

其他操作大同小异，基本上就是分裂+操作，模板：

void qwq(int l,int r,int qaq)
{
    set<node>::iterator itr=split(r),itl=split(l);
    for(set<node>iterator it=itl;it!=itr;it++) do;
}

练手板子题

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long

int n,m,seed,vmax,a[100005];

struct node
{
    int l,r;//左右端点
    mutable int v;//区间值
    friend bool operator < (node a,node b)
    {
     return a.l<b.l;//按左端点排序
    }
};

set<node> s;

set<node>::iterator split(int pos)
{
    set<node>::iterator it=s.lower_bound(node{pos,0,0});//lower_bound重载运算符是根据左端点定位it，所以与r、v无关，r、v是多少都无所谓 
    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);//清空当前set准备分裂
    s.insert(node{l,pos-1,v});
    return s.insert(node{pos,r,v}).first;
}

int quickpow(int a,int b,int p)
{
    int t=1,aa=a%p;
    while(b)
    {
        if(b%2==1) t=t*aa%p;
        aa=aa*aa%p;
        b/=2;
    }
    return t;
}

void assign(int l,int r,int x)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node{l,r,x});
}

struct nodee
{
    int id,cnt;
    bool friend operator < (nodee a,nodee b)
    {
    	return a.id<b.id;
    }
};

int rankk(int l,int r,int x)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    vector<nodee> vv;
    for(set<node>::iterator it1=itl;it1!=itr;it1++) vv.push_back(nodee{it1->v,it1->r-it1->l+1});
    sort(vv.begin(),vv.end());
    int i;
    for(i=0;i<vv.size();i++)
    {
    	if(vv[i].cnt<x) x-=vv[i].cnt;
    	else break;
    }
    return vv[i].id;
}


void add(int l,int r,int x)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    for(set<node>::iterator it3=itl;it3!=itr;it3++) it3->v+=x;
}

int rnd()
{
    int ret=seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}

int cal(int l,int r,int x,int y)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    int ans=0;
    for(set<node>::iterator it2=itl;it2!=itr;it2++) 
    	ans=(ans+quickpow(it2->v,x,y)*(it2->r-it2->l+1)%y)%y;
    return ans;
}

signed main()
{
    cin>>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;i<=m;i++)
    {
        int op,l,r,x,y;
        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) 
        {
        	cout<<rankk(l,r,x)<<endl;
        } 
        else 
        {
        	cout<<cal(l,r,x,y)<<endl;
        }
    }
    return 0;
}