【学习笔记】珂朵莉树(ODT)
2024-10-20 17:20:07
珂朵莉树
\(\tt 0x00\) 起源
起源于 CodeForces 的一题 CF896C,当时出题人提供了这种做法,在随机数据下均摊复杂度比较优秀。
正统名字好像叫颜色段均摊,由于题目也得名于 \(\overset{\tt{Old}}{\texttt{珂}}\overset{\tt{Driver}}{\texttt{朵}}\overset{\tt{Tree}}{\texttt{莉}}\texttt{树}\)。
\(\tt 0x01\) 基本结构
先看代码:
struct node{
ll l,r;
mutable ll v;
node(ll _l,ll _r=0,ll _v=0): l(_l),r(_r),v(_v){}
bool operator<(const node &rhs)const{
return l<rhs.l;
}
};
set<node> s;
结构体中的 \(l,r\) 指数列中 \([l,r]\) 段的左右端点,\(v\) 指这一段表示的数字。
\(\tt{mutable}\) 可让只读迭代器修改其中 \(v\) 的值。
重载运算符 <
的用意是让所有区间按照左端点从小到大排序。
例如原数列为
经过颜色均摊之后,形成的珂朵莉树是这样的:
\(\tt 0x02\) split
珂朵莉数核心操作:split
,作用是以 \(pos\) 为分界线,把 \([l,r]\) 分为 \([l,pos-1]\) 和 \([pos,r]\) 两段,函数的返回值是指向 \([pos,r]\) 的迭代器。
为省时间且好写,set<node>::iterator
可以 typedef
一下或直接用 auto
(C++14 及以后)。
代码:
auto split(int pos){
auto it=s.lower_bound(node(pos)); //按 l 找包含 pos 的 node
if(it!=s.end() && it->l==pos) return it; //找到且为区间左端点,直接返回
it--;//要么没找到,要么是包含 pos 的 node 的后一个 node
if(it->r<pos) return s.end(); //没找到,返回
ll l=it->l,r=it->r,v=it->v; //复制一份
s.erase(it); //删掉这个区间
s.insert(node(l,pos-1,v)); //插入左区间
return s.insert(node(pos,r,v)).first; //插入右区间,并返回右区间的迭代器
}
\(\tt 0x03\) assign
对应区间推平操作。因为我们的 \([l,r]\) 可能包含在其他区间内,所以我们要先把 \(l,r\) split
出来,然后删除中间的所有节点,最后插入一个 \((l,r,v)\) 即可。
注意分裂时要先 split(r+1)
再 split(l)
,不然可能会导致原来指向 split(l)
的迭代器释放,造成 RE。
代码:
void assign(ll l,ll r,ll x){
auto itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,x));
}
\(\tt 0x04\) 其他操作
基本都是套板子:
void modify(ll l,ll r,ll x){
auto itr=split(r+1),itl=split(l);
for(auto it=itl;it!=itr;it++)
// do sth
}
\(\tt 0x05\) 例题
- https://www.luogu.com.cn/problem/CF896C (梦开始的地方)
- https://www.luogu.com.cn/problem/SP13015 (前置知识:素数筛)
- https://www.luogu.com.cn/problem/SP19568 (上一题加强版,加了单点修改操作)
- https://www.luogu.com.cn/problem/CF915E (珂朵莉树板子)
\(\tt 0x06\) 完整代码
最新文章
- SQL中几个常用的排序函数
- geotrellis使用(十五)使用Bokeh进行栅格数据可视化统计
- 怎样学习Java
- FastFDFS_Jave客户端调用(亲测可用)
- Java:多线程<;四>; Lock、停止线程、守护线程、join、优先级&;yield
- CSS用类选择器在本页写样式
- Java Hour 38 Weather ( 11 ) &ndash; fastjson
- Python常用内建模块
- O(1)检测2的幂次
- 如何定制 Calico 网络 Policy - 每天5分钟玩转 Docker 容器技术(70)
- 函数的创建与区别和 prototype
- spring jpa 语法
- 搞Java
- Connection failed Flowsocketconnector Failed to connect to target addressWindows error10061:由于目标计算机积极拒绝,无法连接
- C#简单画图程序
- 笨办法学Python - 习题4: Variables and Names
- P2303 [SDOi2012]Longge的问题
- 关于未来IT职业教育的思考
- webservice-之使用axis+spring开发
- Oracle IMPDP导入数据案例之注意事项(undo/temp)
热门文章
- ssh登录提示hosts is down
- Sublime Text怎样自定义配色和主题
- Python基础部分:3、 pycharm的下载与使用
- Codeforces Round #832 (Div. 2) A-D
- Oracle数据泵导入dmp文件,报UDI-12154、ORA-12154错误解决办法
- Karmada大规模测试报告发布:突破100倍集群规模
- Mysql InnoDB多版本并发控制MVCC
- .NET周报【11月第2期 2022-11-15】
- 操作系统课程设计pintos project1实验摘记
- MediatRPC - 基于MediatR和Quic通讯实现的RPC框架,比GRPC更简洁更低耦合,开源发布第一版