颜色段均摊
反正
ODT！
对于 ODT 来说，其区间推平的复杂度是 \(O((n + m) \log n)\) 的，十分的优秀，但是对于查询来说，我们需要通过分块或者线段进行辅助，从而达到正确的复杂度。
判断是否可以均摊，我们可以看是否能够构造出一个操作序列使得序列复原，如果可以复原，那么基本是不可以均摊的。
或者我们看是否能找到一个量，不增，或者不减，或者有一个神秘的上界，再抽象一点说，存在某一个势能在我们可接受复杂度内。
CF444C - DZY Loves Colors
- 区间赋值
- 区间权值求和
对于区间赋值来说，ODT 所谓的颜色段均摊可以很好做到 \(O((n + m) \log n)\) 的复杂度。
但是我们唯一担心的是查询权值的复杂度，这是很难接受的！
所以我们需要通过线段树进行辅助：考虑到区间赋值对权值带来的影响是区间加，所以利用线段树维护即可。
乍一眼看上去是 \(O(n \log n + m \log^2 n)\) 的复杂度（加上了修改时线段树的复杂度），但是考虑到实际上，每新增或者减少一个颜色段，只会在线段树上区间加一次，也就是说 \(O(n + m)\) 个颜色段带来的是 \(O((n + m) \log n)\) 的线段树操作，所以仍然是一个 \(\log n\) 的。
提交记录：https://codeforces.com/problemset/submission/444/233908238
CF453E - Little Pony and Lord Tirek
这下操作可能困难了。
这道题其实就是所谓的特殊情况：
也就是说，我们在区间推平的时候顺便维护一下这一段的答案即可。
现在的问题转化为经过 \(t\) 时刻后，\([l, r]\) 的权值和。
如果没有对于 \(m_i\) 取 \(\min\) 是简单的，我们需要想办法绕开它。
考虑权值关于时间的函数实际上是分段的：
\[f_i(t) = \begin{cases} 0, & r_i = 0 \\ r_i \times t, & t \le \lfloor \frac {m_i}{r_i} \rfloor \\ m_i, & otherwise \end{cases} \]考虑到 \(\frac {m_i} {r_i} \le 10^5\)，所以可以据此建立可持久化线段树，查询区间即可。
注意由于我们维护的是一次函数，所以需要 \(K, B\) 两棵线段树。
提交记录：https://codeforces.com/contest/453/submission/233920307
P5066 [Ynoi2014] 人人本着正义之名
很套路的是将连续的 \(01\) 段缩成一段，但是呢？
考虑到每次操作，可能造成如下的影响：
- 一些 \(0\) 段长度 \(\pm 1\)
- 一些 \(1\) 段长度 \(\pm 1\)
考虑到区间长度在变化，我们可以通过平衡树维护，例如 wblt。
但是我们会发现存在一个段长度变为 \(0\) 的情况，此时这个区间应当被删除，不再使用。
所以我们需要快速的找到是否需要删除某个区间，这容易利用在平衡树上维护两者的最短长度实现。如果发现了变为 \(0\) 的段，在线段树上二分下去删除它即可。
考虑这样的段一共有 \(O(n)\) 段，每次删除代价是 \(O(\log n)\) 的，总复杂度是 \(O(n \log n)\)，可以接受。
每次操作也是 \(O(\log n)\) 的，总复杂度便是 \(O(n \log n + m \log n)\)，十分优秀。
标签：log,线段,42,算法,复杂度,权值,区间,均摊 From： https://www.cnblogs.com/jeefy/p/17852546.html