珂朵莉树（超详解！）

绪言：研究珂朵莉树的原因

总是看到好多大佬在研究这个十分二次元化的东西（对于我这种男性 OIer 是这个感觉），所以想深入了解一下。

珂朵莉树的起源

珂朵莉树原名老司机树(Old Driver Tree，ODT)，是一种基于std::set的暴力数据结构，由2017年一场CF比赛中提出的数据结构，因为题目背景主角是《末日时在做什么？有没有空？可以来拯救吗？》的主角珂朵莉，因此该数据结构被称为珂朵莉树。

应用

解决各种线段树无法完成的操作。

注意珂朵莉树保持复杂度主要依靠assign操作，所以题目中必须有区间赋值。

还有很重要的一点：数据需纯随机。

什么时候用珂朵莉树

关键操作：推平一段区间，使一整段区间内的东西变得一样。保证数据随机。

n个数，m次操作。 \(n,m\leq10^5\)

操作：

  • 区间加

  • 区间赋值

  • 区间第k小

  • 求区间幂次和

  • 数据随机，时限2s。

构造

用一个带结构体的集合(std::set)维护序列

集合中的每个元素有左端点，右端点，值

下面展示该结构体的构造:

struct Node{
	int l, r;
	mutable int val;
	Node(int a = -1, int b = -1, int c = 0){
		l = a, r = b, val = c;
	}
	bool operator < (const Node &a){
		return l < a.l;
	}
};

//mutale,意为可变的，即不论在哪里都是可修改的，用于突破C++带const函数的限制。

Split

set::iterator split(int pos)

将原来含有pos的区间分为[l,pos)和[pos,r]两段。

返回一个std::set的迭代器，指向[pos,r]段

可能有些抽象，详细解如下:

split函数的作用就是查找set中第一个左端点不小于pos的结点，如果找到的结点的左端点等于pos便直接返回指向该结点的迭代器，如果不是，说明pos包含在前一个结点所表示的区间之间，此时便直接删除包含pos的结点，然后以pos为分界点，将此结点分裂成两份，分别插入set中，并返回指向后一个分裂结点的迭代器。

首先我们假设 set 中有三个node结点，这三个结点所表示的区间长度为14 ，如下图：

不妨以提取区间 [10,12] 为例详细展开（（躁动的读者）诶，说好的查询10到12呢，怎么下面扯了一堆13？别急，后续将会揭晓 ）：

如果我们要查询序列第13个位置，首先执行si it = s.lower_bound(node(13)); 此时it将成为一个指向第三个结点的迭代器，为什么是第三个结点，而不是第二个结点呢，因为lower_bound这个函数获取的是第一个左端点l不小于13的结点，所以it是指向第三个结点的。

然后执行判断语句，发现第三个结点的左端点不是13，不满足条件，说明13必包含在前一个结点中，继续向下执行，让it指向前一个结点：

先将该结点的信息保存下来：int l = 10, r = 13, val = 2
然后直接删除该结点

以pos为分界点，将被删除的结点分裂为 [l,pos-1] ,[pos,r]这两块，并返回指向[pos,r]这个区间的迭代器，事实上return s.insert(node(pos,r,val)).first; ，便做到了插入[pos,r]这端区间，并返回指向它的迭代器，有一个insert函数返回值为pair类型，其中pair的第一个元素就是元素插入位置的迭代器。

至此13位置已经分裂完成，然后是查询第10个位置，查询步骤同上，但是10号点满足if语句，便直接返回了

由上述步骤，为了提取区间 [10,12]，我们执行了两次 split ，一次为split(13),一次为split(10)，并获得了两个迭代器，一个指向第二结点，一个指向第三结点。

为什么要先分裂右端点，然后再分裂左端点呢？

因为如果先分裂左端点，返回的迭代器会位于所对应的区间以 l 为左端点，此时如果r也在这个节点内，就会导致分裂左端点返回的迭代器被 erase 掉，导致 RE

结合问题1和问题2 ，获取区间迭代器时，务必写成如下格式 si itr = split(r+1), itl = split(l); 起名无所谓，按自己的习惯就好

代码

set::iterator split(int pos){
	set::iterator it = st.lower_bound(Node(pos));
	if (it != st.end() && it->l == pos) return it;
	--it; Node tmp = *it; st.erase(it);
	st.insert(Node(tmp.l, pos - 1, tmp.val));
	return st.insert(Node(pos, tmp.r, tmp.val)).first; //first return iterator
}

Assign

注意:以后在使用split分裂区间的时候，请先右后左

区间赋值操作，也是珂树维持其复杂度的关键函数

很暴力的思想，既然刚刚我们写了一个split，那么就要把它用起来。
首先split出l并记返回值为itl，然后split出r+1并记返回值为itr，显然我们要操作的区间为[itl,itr)，那么我们将[itl,itr)删除(std::set.erase(itl, itr))，再插入一个节点Node,其l为l，r为r，val为赋值的val。

我们注意到因为这个操作， [itl,itr)中的所有节点合并为了一个节点，大大降低了集合的元素数量，因此调整了我们的复杂度

void assign(int l, int r, long long val){
	set::iterator itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert((Node){l, r, val});
}
//将一个区间全部改为某个值。

其他操作

通用方法是split出l，split出r+1，然后直接暴力扫描这段区间内的所有节点执行需要的操作

例如我们的区间和查询：

long long querySum(int l, int r){
    set::iterator itr = split(r + 1), itl = split(l); long long res = 0;
    for (set::iterator it = itl; it != itr; ++it)
        res += (it->r - it->l + 1) * it->val;
    return res;
}

例如我们的区间加：

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

例如我们的区间第k小：

前置需要

algorithm库中的std::sort(快速排序)

std::map(方便起见使用其中的pair),std::vector(方便起见)

还是split出l，split出r+1，然后将每个节点的值和个数(即r-l+1)组成一个pair(注意为了排序，将值放在第一关键字)，将pair加入一个vector中

将vector排序

从vector的begin开始扫描，不停的使k减去vector当前项的第二关键字，若 \(k\leq0\)，返回当前项的第一关键字。

long long queryKth(int l, int r, int k){
    vector< pair > vec(0);
    set::iterator itr = split(r + 1), itl = split(l);
    for (set::iterator it = itl; it != itr; ++it)
        vec.push_back(make_pair(it->val, it->r - it->l + 1));
    sort(vec.begin(), vec.end());
    for (vector< pair >::iterator it = vec.begin(); it != vec.end(); ++it)
        if ((k -= it->second) <= 0) return it->first;
    return -1; //note:if there are negative numbers, return another impossible number.
}

求区间所有数的x次方的和模y的值

//快速幂取模
ll qpow(ll a,int b,ll m){
    ll t = 1ll;
    a %= m;
    while(b){
        if(b&1) t= (t*a)%m;
        a = (a*a)%m;
        b>>=1;
    }
    return t;
}
//提取区间，暴力运算
ll query(int l,int r,int x,int y){
    si itr=split(r+1),itl=split(l);
    ll res(0);
    for(si it=itl;it!=itr;++it)
        res=(res+(it->r-it->l+1)*qpow(it->val,x,y))%y;
    return res;
}

珂朵莉树代码样例

#include 
#include 
#include 
#include 
#include 

using namespace std;

//build
struct Node{
    int l, r;
    mutable long long val;
    Node(int a = -1, int b = -1, long long c = 0){
        l = a, r = b, val = c;
    }
    bool operator < (const Node &a) const{
        return l < a.l;
    }
};

set st;

//modify
set::iterator split(int pos){
    set::iterator it = st.lower_bound(Node(pos));
    if (it != st.end() && it->l == pos) return it;
    --it; Node tmp = *it; st.erase(it);
    st.insert(Node(tmp.l, pos - 1, tmp.val));
    return st.insert(Node(pos, tmp.r, tmp.val)).first; //first return iterator
}

void assign(int l, int r, long long val){
	set::iterator itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert((Node){l, r, val});
}

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

//query
long long querySum(int l, int r){
    set::iterator itr = split(r + 1), itl = split(l); long long res = 0;
    for (set::iterator it = itl; it != itr; ++it)
        res += (it->r - it->l + 1) * it->val;
    return res;
}

long long queryKth(int l, int r, int k){
    vector< pair > vec(0);
    set::iterator itr = split(r + 1), itl = split(l);
    for (set::iterator it = itl; it != itr; ++it)
        vec.push_back(make_pair(it->val, it->r - it->l + 1));
    sort(vec.begin(), vec.end());
    for (vector< pair >::iterator it = vec.begin(); it != vec.end(); ++it)
        if ((k -= it->second) <= 0) return it->first;
    return -1; //note:if there are negative numbers, return another impossible number.
}

int main(){
	
    return 0;
}

例题详解CF896C

一说起区间维护问题，我们就能想到线段树，主席树，树状数组，Splay，分块，莫队等数据结构，但是读完题目我们发现，第四个操作涉及每个数字的相关操作，上面提到的结构只有莫队可以做到，但是复杂度太高，我们需要一个更加高效的数据结构 珂朵莉来维护这些操作。

#include 
#include 
#include 
#include 
#include 

using namespace std;

long long read(){
    long long x = 0; int zf = 1; char ch = ' ';
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') zf = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
}

namespace Qpow{
	long long pow(long long a, long long b, long long mod){
		if (!a) return 0;
		long long res = 1; a %= mod;
		for ( ; b; (a *= a) %= mod, b >>= 1ll)
			if (b & 1) (res *= a) %= mod;;
		return res;
	}
};

//build
struct Node{
    int l, r;
    mutable long long val;
    Node(int a = -1, int b = -1, long long c = 0){
        l = a, r = b, val = c;
    }
    bool operator < (const Node &a) const{
        return l < a.l;
    }
};

set st;

//modify
set::iterator split(int pos){
    set::iterator it = st.lower_bound(Node(pos));
    if (it != st.end() && it->l == pos) return it;
    --it; Node tmp = *it; st.erase(it);
    st.insert(Node(tmp.l, pos - 1, tmp.val));
    return st.insert(Node(pos, tmp.r, tmp.val)).first; //first return iterator
}

void assign(int l, int r, long long val){
	set::iterator itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert((Node){l, r, val});
}

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

//query
long long querySum(int l, int r){
    set::iterator itr = split(r + 1), itl = split(l); long long res = 0;
    for (set::iterator it = itl; it != itr; ++it)
        res += (it->r - it->l + 1) * it->val;
    return res;
}

long long querySumWithPow(int l, int r, long long x, long long mod){
    set::iterator itr = split(r + 1), itl = split(l); long long res = 0;
    for (set::iterator it = itl; it != itr; ++it)
        (res += (it->r - it->l + 1) * Qpow::pow(it->val, x, mod)) %= mod;
    return res;
}

long long queryKth(int l, int r, int k){
    vector< pair > vec(0);
    set::iterator itr = split(r + 1), itl = split(l);
    for (set::iterator it = itl; it != itr; ++it)
        vec.push_back(make_pair(it->val, it->r - it->l + 1));
    sort(vec.begin(), vec.end());
    for (vector< pair >::iterator it = vec.begin(); it != vec.end(); ++it)
        if ((k -= it->second) <= 0) return it->first;
    return -1; //note:if there are negative numbers, return another impossible number.
}

long long seed;
long long a[100005];

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

int main(){
	int n = read(), m = read(); seed = read(); long long vmax = read();
	for (int i = 1; i <= n; ++i){
		a[i] = (rnd() % vmax) + 1;
		st.insert((Node){i, i, a[i]});
	}
	long long x, y;
	for (int i = 1; i <= m; ++i){
	    int op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1;
	    if (l > r){int tmp = l; l = r, r = tmp;}
	    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("%I64d\n", queryKth(l, r, x));
	    else if (op == 4) printf("%I64d\n", querySumWithPow(l, r, x, y));
	}
    return 0;
}

相关

标签