首页 > 其他分享 >珂朵莉树

珂朵莉树

时间:2024-09-03 13:55:34浏览次数:2  
标签:www cn 朵莉树 split 端点 区间

经典题(珂朵莉树的诞生):https://www.luogu.com.cn/problem/CF896C

参考:https://www.luogu.com.cn/article/yfcae6d6

不用知道它的具体复杂度,主要是学习如何实现。

珂朵莉树(Chtholly Tree),又名老司机树 ODT(Old Driver Tree)。

split pos 区间分割操作,也就是将包含 pos 的区间分割为两端。

assign l r 区间合并操作,先 split lsplit r+1,然后将中间部分暴力合并(全部删除,然后插入一个整体的区间)

所有区间操作都可以套这样的一个模板:

  • split 右端点,再 split 左端点,获得两个端点(左闭右开)的迭代器。
  • 对两个端点之间的所有区间暴力更改。

标签:www,cn,朵莉树,split,端点,区间
From: https://www.cnblogs.com/huangqixuan/p/18394383

相关文章

  • 珂朵莉树/颜色段均摊学习笔记
    珂朵莉树是基于set的数据结构,与线段树、平衡树等树形结构类似,珂朵莉树是用来解决区间问题的很暴力的树形结构该数据结构支持区间推平,即将区间\([l,r]\)赋值为同一个值1.前置知识setset本质是平衡树,所以不会出现重复的元素且会自动排序,部分函数:set<Node>t;//定......
  • 【学习笔记】珂朵莉树
    前言珂朵莉树(ChthollyTree),又名老司机树(OldDriverTree),起源自CF896CWillem,ChthollyandSeniorious。严格来说,珂朵莉树这种想法是基于数据随机的颜色段均摊,而不是一种数据结构,可作为一些题目的暴力做法(因此原题被分到了暴力数据结构的标签),在随机数据下一般效率较高。基......
  • 洛谷 CF896C Willem, Chtholly and Seniorious之珂朵莉树板子
    洛谷CF896C题解传送锚点摸鱼环节Willem,ChthollyandSeniorious题面翻译【题面】请你写一种奇怪的数据结构,支持:\(1\)\(l\)\(r\)\(x\):将\([l,r]\)区间所有数加上\(x\)\(2\)\(l\)\(r\)\(x\):将\([l,r]\)区间所有数改成\(x\)\(3\)\(l\)\(r\)\(x\):输出将\(......
  • 【模板】珂朵莉树
    这是即将推送到OI-wiki的,对于原OI-wiki珂朵莉树页面的重构。作者是我。感谢上一位维护这玩意的人。简介珂朵莉树(ChthollyTree),又名老司机树ODT(OldDriverTree)。起源自CF896C。这个名称指代的是一种“使用平衡树(std::set、std::map等)或链表(std::list、手写链表等)维护颜......
  • [OI] 珂朵莉树
    对于一个序列,它有较多重复元素,并且题目需要维护区间修改,维护区间信息,维护整块值域信息的,那么就可以考虑珂朵莉树解决.主要思想珂朵莉树将全部相同的颜色块压缩为一组,如对于下述序列:111234444珂朵莉树铺平后即可以变为这样:{1,3,1}{4,4,2}{5,5,3}{6,9,4}其中的三......
  • [数据结构] 珂朵莉树
    介绍珂朵莉树,学名珂朵莉树,又学名老司机树($ODT$),常用来解决“区间推平”(把区间改为某一个数)等的操作,只适用于随机数据,可以定向卡掉;其实这玩意就是暴力,没啥可说的,分块都比不上她暴力;但人家毕竟是她,所以对于一些题还是有用的;实现只要你会$C++\STL$里的$set$,搞定她完......
  • 算法学习笔记(18):珂朵莉树
    珂朵莉树这个名字我猜是来源于初次诞生这个算法的题目->Willem,ChthollyandSeniorious算法适用于数据随机,并且有区间推平操作,也就是区间赋值操作,就可以用set维护,达到优秀的\(O(nlogn)\)时间复杂度。定义structNode{ intl,r; mutableintv; Node(intl,intr......
  • 珂朵莉树
    一种特殊的数据结构。介绍李欣隆发明。本质上并不是一种树形数据结构,思想是把一个区间按\(value\)划分成不少的小区间,然后暴力操作。显然,这样做的复杂度完全依赖于小区间的多少,所以复杂度需要由区间推平操作保证。在随机的数据下,可以证明每次的小区间期望有\(\log_2n\)个,......
  • 珂朵莉树ODT 模板
    构造set:structnode{intl,r;mutableintv;node(intl,intr,intv=0):l(l),r(r),v(v){}booloperator<(constnode&a)const{returnl<a.l;}};set<node>s;分裂set:autosplit(intpos){aut......
  • 珂朵莉树
    简介珂朵莉树一般多见于区间推平操作,即把[l,r]区间的值都赋值成k值的区间推平操作,在数据随机中可以出现奇效。模板点击查看代码structnode{intl,r;mutableintv;//mutable相反于const用于操作存于set(存于set的均为const,但是加了mutable即可修改其值)中的值.......