跳到主要内容

珂朵莉树

概述

珂朵莉树又名老司机树（ODT），起源于 CF896C，核心是把值相同的连续区间合并成一个节点存进 set，靠数据随机时区间数很少来保证均摊效率。关键操作是 split：把包含 x 的区间从 x 处劈开并返回右段迭代器；区间赋值 cover 借助两次 split 后 erase 掉整段再插入新节点，把区间数压下来，区间加与区间求和则遍历涉及的节点。提醒求区间端点时必须先 split 右端点再 split 左端点，否则迭代器可能失效导致 RE。例题为 CF896C。

参考资料​

简介​

珂朵莉树（Chtholly Tree），又名老司机树（Old Driver Tree，ODT），起源于 CF896C。

核心思想是将值相同的区间合并为一个节点，并保存在 set 中。

实现​

保存节点​

110 Bcpp
struct Node
{
	int l,r;
	mutable ll v;
	bool operator<(const Node &rhs) const{return l<rhs.l;}
};
set<Node> s;

insert​

18 Bcpp
s.insert({l,r,v});

split​

将包含 xx 的区间 [l,r][l,r] 分裂为区间 [l,x−1][l,x-1] 和区间 [x,r][x,r]，并返回区间 [x,r][x,r] 的迭代器。

186 Bcpp
auto split(int x)
{
	auto it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x)return it;
	it--;
	auto [l,r,v]=*it;
	s.erase(it);
	s.insert({l,x-1,v});
	return s.insert({x,r,v}).first;
}
注意

珂朵莉树在进行求取区间左右端点操作时，必须先 split 右端点，再 split 左端点。

若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，可能会导致 RE。

cover​

106 Bcpp
void cover(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	s.erase(it1,it2);
	s.insert({l,r,v});
}

add​

105 Bcpp
void add(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	for(auto it=it1;it!=it2;it++)it->v+=v;
}

sum​

140 Bcpp
ll sum(int l,int r)
{
	auto it2=split(r+1),it1=split(l);
	ll res=0;
	for(auto it=it1;it!=it2;it++)res+=it->v*(it->r-it->l+1);
	return res;
}

例题​

洛谷 CF896C Willem, Chtholly and Seniorious

请你写一种奇怪的数据结构，支持 44 种操作：

  • 1 l r x：将 [l,r][l,r] 区间所有数加上 xx。
  • 2 l r x：将 [l,r][l,r] 区间所有数改成 xx。
  • 3 l r x：求 [l,r][l,r] 区间的第 xx 小。
  • 4 l r x y：求 [l,r][l,r] 区间每个数字的 xx 次方的和对 yy 取模的值。