珂朵莉树（ODT）学习笔记

对一个序列进行推平和查询等操作，我们难免会有过这样的想法：只维护连续段即可。但是这只是比较优的暴力，精心构造的数据可以轻松卡掉。
事实上，在随机数据下，这样的算法的时间复杂度是 \(\mathcal{O}(n\log n)\)，这就是颜色段均摊理论，证明不会。
根据这个理论产生了珂朵莉树，它可以维护区间推平和查询操作。
具体来说，可以用一些数据结构来维护颜色端，在进行操作时找到相应的颜色段，修改后合并。
珂朵莉树的核心是分裂 split 和合并 assign 操作，大体有三种实现方法。
节点类型：

struct NODE{
	int l,r;mutable int v;
	inline bool operator<(const NODE&a)const{return l<a.l;}
}

std::set 中的元素是静态的，不可改变，而 mutable 可以强制突破 const 的限制，使操作更简洁。

std::set 实现

主流写法。

inline auto split(int x){
	auto it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x)return it;
	--it;
	int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,x-1,v});
	return s.insert({x,r,v}).first;
}

split 函数可以将包含 \(x\) 位置的区间分裂为两个区间，返回后一个区间的迭代器。

inline void assign(int l,int r,int v){
	auto itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert({l,r,v});
}

assign 函数可以将 \([l,r]\) 中的所有区间合并为一个，并区间推平。后 split(r+1) 可能会使 split(l) 失效，所以顺序不能变。

inline void perform(int l,int r){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl){
		// Do Something here
	}
}

perform 函数可以遍历一遍 \([l,r]\) 中的区间，进行相关操作。

std::map 实现

观察上面的代码，发现 NODE 中的右端点并没有起作用，不妨使用 std::<int,int>map 只记录左端点和权值即可，操作更加简洁。

inline auto split(int x){
	auto it=std::prev(mp.lower_bound(x));
	return mp.insert(it,{x,it->second});
}
inline void assign(int l,int r,int v){
	split(l);split(r);auto it=mp.find(l);
	while(it->first!=r)it=mp.erase(it);
	mp[l]=v;
}

链表实现

不会链表

CF896C
CF915E