梗出处：请问您今天要来点兔子吗？
这篇文章主要记录一下自己学习 \(\text{ODT}\) 发生的种种。
CF896C Willem, Chtholly and Seniorious
\(\text{ODT}\) 成名题目，表示 \(\text{lxl}\) 为了防 \(\text{Hack}\) 真的是用心了。
关于 \(\text{ODT}\) 随机情况下的期望时间复杂度，请参考著名某知乎文章。
很暴力的数据结构，assign 操作是核心，剩下的基本上都是暴力区间分离，暴力统计联通区间。
期望时间复杂度 \(\Theta(n \log \log n)\)
P4979 矿洞：坍塌
为数不多 \(\text{ODT}\) 的时间复杂度是正确的题目？
只能说 \(\text{Hack}\) 数据卡了个寂寞。
有一种更加优秀的做法，但是我没想，所以下面给出一个不是很优秀的做法（也可以当做一种 \(trick\)）
发现一共两个操作，一个是 assign 操作，另一个是 query。
考虑时间复杂度最有可能会被摊到哪里，发现是我们亲爱的 query 操作。
因为 assign 操作可能会产生大量的散块，所以我们可以考虑在 query 的时候，对于当前同颜色联通的散块进行一次 assign，然后如果发现当前不合法了 break 维护再跳出，可以看出，这样摊下来时间复杂度会被摊到 \(O(n \log n)\)。
估计这可能也是它评蓝的原因
CF915E Physical Education Lessons
一开始脑瘫了，真的就按照题目给出的条件去硬 query 了。
发现如果硬 query 很容易被卡掉。
所以考虑修改带来的影响，发现每次修改都是 assign 操作，所以就考虑课程数的变化量 \(\Delta\) 就可以了。
然后……就做完了，时间复杂度感觉有点抽象，不是很懂。
P5066 [Ynoi2014] 人人本着正义之名
感觉这个题 \(\text{ODT}\) 很逆天，所以显然只能拿 \(80\) pts。
首先看题，是 \(01\) 序列。
然后发现，两个 assign，一个区间和，还有四个抽象的操作。
考虑那四个抽象的操作是什么：
- 相邻按位与：\(0\) 向相邻方向吞一个。
- 相邻按位或：\(1\) 向相邻方向吞一个。
然后……就是 \(ODT\) 维护了。
当然，正解是平衡树。