珂朵莉树 珂朵莉树（老司机树/ODT）是一种由李欣隆发明的暴力数据结构，在随机数据下表现良好。珂朵莉树主要用于有着大量区间推平操作的题目，但是在构造数据下表现十分不好。如果区间推平操作较多，则单一操作的时间复杂度为\(O(\log_2n)\)。在特殊构造下，单一操作则会退化成\(O(n\log^2_2n)\)。 前置芝士 set的应用。懂得set的迭代器用法。 做法 首先珂朵莉树的前提条件就是基于推平操作。也就是将\([l,r]\)全部修改成\(x\)。所以最终整个序列会变成一个一个段，每个段的元素值均为\(x\)。我们要做的就是维护这个东西。 所以我们首先要定义一个结构体，里面存\(l,r,...

符号规定 先来规定一些符号。 \(\lvertS\rvert\)代表这个字符串\(S\)的长度。 \(S_{l\cdotsr}\)代表字符串从第\(l\)个字符到第\(r\)个字符组成的字串。 \(F(S,i)\)等同于\(S_{1\cdotsi}\)（就是字符串长度为\(i\)的前缀） \(E(S,i)\)等同于\(S_{\lvertS\rvert-i+1\cdots\lvertS\rvert}\)（就是字符串长度为\(i\)的后缀）注意在我们的定义里这个后缀是从左往右读的 \(B(S)\)表示\(S\)的一个最长border的长度（具体什么是border之后再谈） 前置芝士—borde...