颜色段均摊

反正 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)$，十分优秀。