脚本宝典收集整理的这篇文章主要介绍了【学习笔记】ODT，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

复习笔记（

学习 (ODT) 怎么能没有珂朵莉呢qwq（大雾）

【模板题】CF896C Willem, Chtholly and Seniorious

简介

(ODT) ， 又名珂朵莉树，一种比较暴力的数据结构，基于 (STL) 里的 (set) 实现，其核心思想就是将相同值的区间合并成一个节点，对于某些需要区间修改的题目有奇效，但是要求数据一定要随机，否则就会退化为暴力qwq

优点：码量少，操作简单，易查错，在数据随机的情况下效率高

缺点：需要题目包含区间修改操作，容易被卡，在数据不随机的情况下会退化成暴力

实现

1、初始化

用结构体来储存节点信息。

struct node{
	int l,r;//这个节点所包含的区间
	mutable int v;//这个节点的值
	node(int _l,int _r=0,int _v=0){l=_l;r=_r;v=_v;}
	bool operator < (const node &amp;a) const {return l<a.l;}
    //将区间按顺序排好
};

如何理解每一个节点呢？

假设有这么一段数列

1 1 1 1 4 4 3

那么我们就会构建三个节点，分别如下：

id:1 -> l=1 r=4 v=1
id:2 -> l=5 r=6 v=4
id:3 -> l=7 r=7 v=3

但是在一开始输入初始数组时，我们仅需对于每一个值建立一个节点，相同值的合并可以留到后面的操作来处理。

下面要注意有一个点，这里有个 mutable ，由于在 (set) 中，元素是以常量方式储存的，我们无法对其直接进行修改，因为 (set) 里面元素的排列顺序是个根据 (l) 的大小，与 (v) 无关，所以我们可以加个 mutable 来直接修改 (v) ，否则就要先删除元素再插入元素，降低了效率。

接着再

set<node> odt;

就行了

2、(SlpIT) 操作

这是 (ODT) 的核心操作之一，当某处需要修改时，发现这一处包含在一个节点之内，如何处理？我们就需要将这个节点拆成两部分。

假如我们 (Split(i)) ，且 (i) 包含在区间 ([l,r]) 中，那么执行 (Split) 操作之后这个区间就会分为 ([l,i-1]) 和 ([i,r]) 这两个区间，接着就可以愉快地进行修改或查询了。

#define iter set<node>::iterator
iter Split(int x)
//注意我们返回的是一个迭代器方便查找修改
{
	if(x>n) return odt.end();
    //如果查询的位置大于n就不必分裂

	iter it=--odt.upPEr_bound(node(x));
    //找到包含x的区间，即找到包含x的区间的左端点

	if(it->l==x) return it;
    //为左端点不必分裂

	int l=it->l,r=it->r,v=it->v;
    //先将节点的信息取出来
	odt.erase(it);
    //删掉节点

	odt.insert(node(l,x-1,v));
    //插入前半段[l,x-1],值为v
	return odt.insert(node(x,r,v)).First;
    //插入后半段，再返回后半段的迭代器
}

3、(assign) 操作

这也是 (ODT) 的核心操作之一，是实现区间合并的主要操作

void Assign(int l,int r,int v)
//将区间[l,r]都改为v且保存到一个节点
{
	iter itr=Split(r+1),itl=Split(l);
    //找出修改区间的起点和终点
	odt.erase(itl,itr);
    //删除区间[l,r+1)
	odt.insert(node(l,r,v));
    //插入节点
}

这里有个细节，对于分裂区间 ([l,r+1)) 要先执行 Split(r+1) ，再执行 Split(l)

假如 (l) 和 (r) 均包含在区间 ([L,R]) 。

我们先 Split(l) ，那么某段区间就会分解为 ([L,l-1]) 和 ([l,R]) ，并且返回 ([l,R]) 的迭代器；

接着 Split(r+1) ，这时就会将 ([l,R]) 分解为 ([l,r-1]) 和 ([r,R]) ，并且删除 ([l,R]) 的迭代器，第一次返回的迭代器被删除了，这时就会导致 (Re)

所以切记，先执行 Split(r+1) ，再执行 Split(l) qwq

3、其他操作

区间加

分裂后直接暴力（

#define iter set<node>::iterator
void add(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) 
        itl->v+=val;
}

区间第 (k) 小

取出区间直接 (sort) (

#define iter set<node>::iterator
struct Rank{
	int num,cnt;
	Rank(int _num,int _cnt){num=_num;cnt=_cnt;}
	bool operator < (const Rank &a) const {return num<a.num;}
};
int askrank(int l,int r,int k)
{
	iter itr=split(r+1),itl=split(l);
	vector<Rank> ve;
	for(;itl!=itr;++itl) 
        ve.push_back(Rank(itl->v,itl->r - itl->l + 1));
	sort(ve.begin(),ve.end());
	int i=0;
	for(;i<ve.size();++i)
		if(ve[i].cnt<k)
			k-=ve[i].cnt;
		else break;
	return ve[i].num; 
}

至于说为什么用 (vector) ，学着别人写的（（

区间 (N) 次方和

这个询问有点神奇，恐怕其他数据结构没法处理qwq

对于 (ODT) 还是暴力（

#define iter set<node>::iterator
int askpower(int l,int r,int b,int p)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0;
	for(;itl!=itr;++itl) 
		ans+=(Power(itl->v,b,p)*(itl->r - itl->l + 1)%p),ans%=p;
	return ans;
}
//Power(a,b,p)为快速幂，求a^b%p

---

反正对于什么修改询问操作，都这么搞

#define iter set<node>::iterator
void qwq(int l,int r,...)
{
    iter itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        ...
        //一通乱搞（
    }
}

总结

其实 (ODT) 就是一种优化的暴力，优化的思想也挺容易的。

如果保证数据随机，那么区间个数并不会太多，差不多是在 (LOG) 级别的，复杂度也就是 (O(MLogn)) ，起伏并不会太大。

关于详细的复杂度证明可以看这篇文章 珂朵莉树的复杂度分析

对于数据随机的题目可以试着打棵 (ODT) ，能和一般的数据结构匹敌，甚至出现意想不到的结果。但如果数据不随机，出题人造数据时可以将区间的大小缩小， (ODT) 所储存的区间个数就会增大，硬生生卡成暴力，然后出现意想不到的结果（

总的来说，平常刷题是可以将 (ODT) 当正解打，但是在考场上千万不要完全依靠 (ODT) ，你可以拿它来骗分，骗分的多少就是运气，但是如果时间充裕的话还是骗完分后想想正解吧qwq

参考资料：

OI Wiki

脚本宝典总结

以上是脚本宝典为你收集整理的【学习笔记】ODT全部内容，希望文章能够帮你解决【学习笔记】ODT所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。