经典题(珂朵莉树的诞生):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 l
再 split r+1
,然后将中间部分暴力合并(全部删除,然后插入一个整体的区间)
所有区间操作都可以套这样的一个模板:
- 先
split
右端点,再split
左端点,获得两个端点(左闭右开)的迭代器。 - 对两个端点之间的所有区间暴力更改。