ODT 学习笔记「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

珂朵莉，要一直幸福下去哟！

warning：本文在大白天书写，脑子可能不大好用。

目前代码选自题解，等有时间自己写一下。

简介

ODT（Old Driver Tree（中文译名张舟树），又称 Chtholly Tree，即众人皆知的珂朵莉树） 是一种非常暴力的思想或者做法 （注意我没有说是数据结构）

简单来说，其核心思想是把一段区间推平（这也是其适用的地方——区间赋值），推平之后，原数列变成一段一段的了（每段的数值相同），然后就可以搞事了。

ODT 在随机数据下，复杂度近似 O ( m l o g n ) O(m log n) O(mlogn)，证明请自行翻参考资料。

前置知识

熟练使用 STL（至少要熟练使用 set）或者会写平衡树。

初始化

我们维护一个结构体 n o d e node node，包含 l , r , d l,r,d l,r,d （ d d d 是题目要求维护的值），表示一个被推平的区间。

代码语言：javascript复制

struct node{ 
   
	ll l,r;
	mutable ll v;
	node(ll l,ll r=0,ll v=0):l(l),r(r),v(v){ 
   };
	inline operator <(const node &a)const{ 
   
		return l<a.l;
	}
};

有意思的一个结论：只要没有线段被另一条线段完全覆盖，那么按左端点排序后右端点同样有序。

mutable 可以看成 const 的反义词，被 mutable 修饰的变量不受 const 的影响，一直变化。

注：下文的“复杂度”均指在随机数据下。

split 操作

ODT 两大核心操作之一，用处是当出现某些修改操作后，我们推平的区间将被分裂（一个区间中必须值相同），这个时候这个区间就会被分裂成两个。也就是 [ l , p o s − 1 ] [l,pos-1] [l,pos−1] 和 [ p o s , r ] [pos,r] [pos,r]

代码语言：javascript复制

#define IT set<node>::iterator
IT split(int pos){ 

IT it=s.lower_bound(node(pos));//求前驱
if(it!=s.end()&&it->l==pos)return it;//如果it的l值就是左端点，换句话说pos的位置恰好是l，就不需要分裂了
it--;//见上
int L=it->l,R=it->r;ll V=it->v;
s.erase(it);//彻底抹掉
s.insert(node(L,pos-1,V));//先建[l,pos-1]
return s.insert(node(pos,R,V)).first;//然后建[pos,r]，同时返回后半段区间的迭代器
}

复杂度为 O ( l o g n ) O(log n) O(logn)

assign 操作

ODT 两大核心操作之二，也就是推平一个区间，说起来比较高大上，其实就是区间赋值。

代码语言：javascript复制

void assign(int l,int r,int val=0){ 

IT itr=split(r 1),itl=split(l);//注意一定要先split r 1
s.erase(itl,itr);
s.insert(node(l,r,val));//先删除小区间，直接覆盖为大区间 
}

其他操作

ODT 有点技术含量的操作就这俩，剩余都是暴力（字面意思），下面以 梦 开 始 的 地 方 （目前看来也是梦结束的地方）——CF896C为例介绍一下。

首先是所有操作的套路，先 split 一下右端点，再 split 一下左端点，得到两个端点的迭代器，然后直接暴力求解。

比如区间加：

代码语言：javascript复制

void add(int l, int r, LL k=1)
{ 

IT itl=split(l),itr=split(r 1);
for(;itl!=itr;  itl) 
itl->v =k;
}

当我第一次看到这个操作时我的内心想法：

代码语言：javascript复制

珂朵莉树区间加很暴力是怎么回事呢？珂朵莉树相信大家都很熟悉，但是珂朵莉树区间加很暴力是怎么回事呢，下面就让小编带大家一起了解吧。
　　珂朵莉树区间加很暴力，其实就是珂朵莉树就是暴力，大家可能会很惊讶珂朵莉树怎么会区间加很暴力呢？但事实就是这样，小编也感到非常惊讶。
　　这就是关于珂朵莉树区间加很暴力的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

再比如说区间幂次，这个有意思，主流数据结构（*队，线*树,**树）都做不到一个优秀的复杂度（小声：在随机数据下）

代码语言：javascript复制

ll sum(int l,int r,int ex,int mod){ 

IT itl=split(l),itr=split(r 1);
LL res=0;
for (;itl!=itr;  itl)
res=(res (LL)(itl->r-itl->l 1)*pow(itl->v,LL(ex),LL(mod)))%mod;
return res;
}

就还是暴力呗。

ODT 有什么特点？容易被卡好写！所以我们在最后介绍这个比较长的操作：区间 k k k 小。

代码语言：javascript复制

ll rank(int l,int r,int k){ 

vector<pair<ll,int> >t;
t.clear();
IT itl=split(l),itr=split(r 1);
for(;itl!=itr;  itl)
t.push_back(pair<ll,int>(itl->v,itl->r-itl->l 1));
sort(t.begin(),t.end());
for(vector<pair<ll,int> >::iterator it=t.begin();it!=t.end();  it){ 

k-=it->second;
if(k<=0)
return it->first;
}
return -1ll;
}

总结

这是一种极其适合骗分的暴力算法，好写，好调。

ODT 就是对暴力的优化，其核心是区间覆盖这个操作，正是区间覆盖让 ODT 焕发生机。

区间覆盖，发生了会如何，不发生又会如何。 在这种困难的抉择下，本人思来想去，寝食难安。 马克思说过一句著名的话，一切节省，归根到底都归结为时间的节省。这句话语虽然很短, 但令我浮想联翩. 既然如此， 可是，即使是这样，区间覆盖的出现仍然代表了一定的意义。 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 问题的关键究竟为何？ 区间覆盖，发生了会如何，不发生又会如何。 在这种困难的抉择下，本人思来想去，寝食难安。 迈克尔·F·斯特利说过一句著名的话，最具挑战性的挑战莫过于提升自我。我希望诸位也能好好地体会这句话. 区间覆盖，到底应该如何实现。 每个人都不得不面对这些问题。 在面对这种问题时， 吕凯特说过一句富有哲理的话，生命不可能有两次，但许多人连一次也不善于度过。这启发了我. 亚伯拉罕·林肯说过一句著名的话，我这个人走得很慢，但是我从不后退。这句话看似简单，但其中的阴郁不禁让人深思. 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 要想清楚，区间覆盖，到底是一种怎么样的存在。 区间覆盖，发生了会如何，不发生又会如何。 可是，即使是这样，区间覆盖的出现仍然代表了一定的意义。 我们一般认为，抓住了问题的关键，其他一切则会迎刃而解。 区间覆盖的发生，到底需要如何做到，不区间覆盖的发生，又会如何产生。 区间覆盖，到底应该如何实现。 我们都知道，只要有意义，那么就必须慎重考虑。 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 问题的关键究竟为何？ 文森特·皮尔在不经意间这样说过，改变你的想法，你就改变了自己的世界。这句话看似简单，但其中的阴郁不禁让人深思. 对我个人而言，区间覆盖不仅仅是一个重大的事件，还可能会改变我的人生。 一般来说， 区间覆盖的发生，到底需要如何做到，不区间覆盖的发生，又会如何产生。 我们都知道，只要有意义，那么就必须慎重考虑。 区间覆盖，发生了会如何，不发生又会如何。 带着这些问题，我们来审视一下区间覆盖。 　　这种事实对本人来说意义重大，相信对这个世界也是有一定意义的。 经过上述讨论， 那么， 杰纳勒尔·乔治·S·巴顿说过一句著名的话，接受挑战，就可以享受胜利的喜悦。这句话把我们带到了一个新的维度去思考这个问题: 我认为， 了解清楚区间覆盖到底是一种怎么样的存在，是解决一切问题的关键。 现在，解决区间覆盖的问题，是非常非常重要的。 所以， 经过上述讨论， 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 区间覆盖，发生了会如何，不发生又会如何。 老子在不经意间这样说过，知人者智，自知者明。胜人者有力，自胜者强。这似乎解答了我的疑惑. 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 既然如何， 一般来讲，我们都必须务必慎重的考虑考虑。 区间覆盖，到底应该如何实现。 从这个角度来看， 而这些并不是完全重要，更加重要的问题是， 可是，即使是这样，区间覆盖的出现仍然代表了一定的意义。 问题的关键究竟为何？ 富兰克林在不经意间这样说过，你热爱生命吗？那么别浪费时间，因为时间是组成生命的材料。带着这句话, 我们还要更加慎重的审视这个问题。 　　这样看来， 那么， 从这个角度来看， 那么， 问题的关键究竟为何？ 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 就我个人来说，区间覆盖对我的意义，不能不说非常重大。 　　那么， 本人也是经过了深思熟虑，在每个日日夜夜思考这个问题。 对我个人而言，区间覆盖不仅仅是一个重大的事件，还可能会改变我的人生。 郭沫若说过一句富有哲理的话，形成天才的决定因素应该是勤奋。这不禁令我深思. 区间覆盖的发生，到底需要如何做到，不区间覆盖的发生，又会如何产生。 既然如此， 带着这些问题，我们来审视一下区间覆盖。 每个人都不得不面对这些问题。 在面对这种问题时。 　　莎士比亚曾经提到过，本来无望的事，大胆尝试，往往能成功。我希望诸位也能好好地体会这句话. 这样看来， 生活中，若区间覆盖出现了，我们就不得不考虑它出现了的事实。 区间覆盖因何而发生？ 问题的关键究竟为何？ 区间覆盖，发生了会如何，不发生又会如何。 左拉在不经意间这样说过，生活的道路一旦选定，就要勇敢地走到底，决不回头。这似乎解答了我的疑惑. 了解清楚区间覆盖到底是一种怎么样的存在，是解决一切问题的关键。 一般来说。 　　在这种困难的抉择下，本人思来想去，寝食难安。 一般来讲，我们都必须务必慎重的考虑考虑。 总结的来说， 区间覆盖因何而发生？ 歌德说过一句著名的话，没有人事先了解自己到底有多大的力量，直到他试过以后才知道。带着这句话, 我们还要更加慎重的审视这个问题: 既然如此， 马克思说过一句著名的话，一切节省，归根到底都归结为时间的节省。这启发了我. 迈克尔·F·斯特利曾经提到过，最具挑战性的挑战莫过于提升自我。带着这句话, 我们还要更加慎重的审视这个问题。

参考资料：

CF896C 的题解

珂朵莉树 OI wiki

珂朵莉树的复杂度分析 知乎

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/197643.html原文链接：https://javaforall.cn

mutable split tree

1 人点赞