Skip to main content

珂朵莉树

参考资料​

简介​

珂朵莉树（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;
}
warning

珂朵莉树在进行求取区间左右端点操作时，必须先 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 取模的值。