前言

珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构，因那道题题面（CF896C）关于珂朵莉而得名。

珂朵莉树适用于以下的情况：维护一个序列，有区间赋值操作，数据随机。下面是珂朵莉树板子题：

维护一个序列，需要支持以下操作

1. 将 $[l,r]$ 区间所有数加上 $x$

2. 将 $[l,r]$ 区间所有数改成 $x$

3. 求 $[l,r]$ 区间第 $k$ 小

4. 求 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\left(\sum_{i=l}^{r} a_{i}^{x}\right) \bmod y$)

– CF896C Willem, Chtholly and Seniorious

支持的操作还可以有很多，只要暴力能做珂朵莉树一般都可以做。

珂朵莉树的思想是维护一堆区间，合并相同值的区间，这样区间总数就可以减少。

珂朵莉树非常依赖区间赋值操作，如果区间赋值操作很少或者区间赋值的区间都较短，那么珂朵莉树和暴力就没什么区别了。

显然，要卡珂朵莉树非常容易。但对于数据完全随机的情况，珂朵莉树就可以跑得飞快。有很多题可以用珂朵莉树水过，甚至比正解还快。

思路

珂朵莉树维护了很多区间。

一个区间表示一段相同的数。一个区间 $(l,r,num)$ 表示从左端点 $l$ 到右端点 $r$，中间的数字全部为 $num$。

例如 $1,2,3,3,3,4,4,5$ 可以用 $5$ 个区间来表示：$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$。

区间赋值的时候，我们可以删去一些区间并用一个大区间代替它们，区间数量就少了很多。

而查询只需要找出相应的区间，然后暴力统计即可。

如果某次操作的边界在某个区间的中心，那么将这个区间断开即可。

我们用 set 维护区间左端点位置的值，使区间始终保持有序。

区间结构体定义

struct node
{
    long long l,r;
    mutable long long num;
    bool operator<(const node y) const
    {
        return l<y.l;
    }
};

Split

Split 操作用来将一个区间断开。

set<node>::iterator split(long long x)
{
    node tmp={x};
    set<node>::iterator it=s.lower_bound(tmp);
    if(it!=s.end()&&it->l==x)
    {
        return it;
    }
    it--;
    long long l=it->l,r=it->r,num=it->num;
    s.erase(it);
    tmp={l,x-1,num};
    s.insert(tmp);
    tmp={x,r,num};
    return s.insert(tmp).first;
}

区间赋值操作 (Assign)

删除该区间所覆盖的所有小区间，并插入一个大区间来代替它们。

void assign(long long l,long long r,long long x)
{
    set<node>::iterator R=split(r+1);
    set<node>::iterator L=split(l);
    s.erase(L,R);
    node tmp={l,r,x};
    s.insert(tmp);
}

查询操作

就是暴力，找出相应区间并暴力统计

区间和

long long query_sum(long long l,long long r)
{
	set<node>::iterator R=split(r+1),L=split(l);
	long long ans=0;
	while (L!=R)
       {
		ans+=L->num*(L->r-L->l+1); //遍历求和
		ans%=y; 
		L++;
	}
	return ans;
}

区间 x 次方和

和求和一样，只是改成快速幂

long long query_pow_sum(long long l,long long r,long long x,long long y)
{
    set<node>::iterator R=split(r+1),L=split(l);
    long long ans=0;
    while(L!=R)
    {
        ans+=qpow(L->num,x,y)*(L->r-L->l+1);
        ans%=y;
        L++;
    }
    return ans;
}

区间第 k 小

取出相应区间内的所有区间排序，从前到后找第 k 小

long long query_kth(long long l,long long r,long long k)
{
    set<node>::iterator R=split(r+1),L=split(l);
    vector<pair<long long,long long> > t;
    while(L!=R)
    {
        t.push_back(make_pair(L->num,L->r-L->l+1));
        L++;
    }
    sort(t.begin(),t.end());
    for(long long i=0;i<t.size();i++)
    {
        k-=t[i].second;
        if(k<=0)
        {
            return t[i].first;
        }
    }
    return -2147483647;
}

其他操作

你应该已经发现了，珂朵莉树其实就是暴力，暴力怎么写珂朵莉树就怎么写，真·暴力数据结构

例题代码

CF896C Willem, Chtholly and Seniorious

#include<bits/stdc++.h>
using namespace std;

long long n,m,seed,vmax;

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

inline long long qpow(long long a,long long b,long long p)
{
    long long ans=1;
    a%=p;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

struct node
{
    long long l,r;
    mutable long long num;
    bool operator<(const node y) const
    {
        return l<y.l;
    }
};

set<node> s;

set<node>::iterator split(long long x)
{
    node tmp={x};
    set<node>::iterator it=s.lower_bound(tmp);
    if(it!=s.end()&&it->l==x)
    {
        return it;
    }
    it--;
    long long l=it->l,r=it->r,num=it->num;
    s.erase(it);
    tmp={l,x-1,num};
    s.insert(tmp);
    tmp={x,r,num};
    return s.insert(tmp).first;
}

void assign(long long l,long long r,long long x)
{
    set<node>::iterator R=split(r+1);
    set<node>::iterator L=split(l);
    s.erase(L,R);
    node tmp={l,r,x};
    s.insert(tmp);
}

long long query_kth(long long l,long long r,long long k)
{
    set<node>::iterator R=split(r+1),L=split(l);
    vector<pair<long long,long long> > t;
    while(L!=R)
    {
        t.push_back(make_pair(L->num,L->r-L->l+1));
        L++;
    }
    sort(t.begin(),t.end());
    for(long long i=0;i<t.size();i++)
    {
        k-=t[i].second;
        if(k<=0)
        {
            return t[i].first;
        }
    }
    return -2147483647;
}

long long query_pow_sum(long long l,long long r,long long x,long long y)
{
    set<node>::iterator R=split(r+1),L=split(l);
    long long ans=0;
    while(L!=R)
    {
        ans+=qpow(L->num,x,y)*(L->r-L->l+1);
        ans%=y;
        L++;
    }
    return ans;
}

void add(long long l,long long r,long long x)
{
    set<node>::iterator R=split(r+1),L=split(l);
    while(L!=R)
    {
        L->num+=x;
        L++;
    }
}

int main()
{
    cin>>n>>m>>seed>>vmax;
    for(long long i=1;i<=n;i++)
    {
        node tmp={i,i,rnd()%vmax+1};
        s.insert(tmp);
    }
    for(long long i=1;i<=m;i++)
    {
        long long op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;
        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)
        {
            assign(l,r,x);
        }
        if(op==3)
        {
            cout<<query_kth(l,r,x)<<endl;
        }
        if(op==4)
        {
            cout<<query_pow_sum(l,r,x,y)<<endl;
        }
    }
}

注：转载自暴力数据结构 : 珂朵莉树 (ODT)

前言

思路