CF1322E 题解
转换为 $01$ 序列的操作其他题解都已经讲的很清楚了，我这里主要提供一种只用线段树来维护答案的方法。
首先是得到操作数。初始序列上是全 $0$ 的，我们从小到大枚举每个数，并把他们修改成 $1$。由于答案是 $01$ 交错段的长度的一半，我们线段树上的每个结点分别维护左部是 $0/1$，右部是 $0/1$，左部交错段的长度，右部交错段的长度，区间内交错段的最大长度。向上转移比较容易。
然后是得到最后的操作序列。如果一个位置在当前位置由 $0$ 变成 $1$ 之后，在操作完后的序列中由 $0$ 变成了 $1$，那么可以认为这个位置在操作完后变成了当前改变的这个位置的值。而一个位置能影响到的位置，只有他改变完后所在的最长 $01$ 段和他左右两个 $1$ 所在的最长 $01$ 段。注意第二部分是很容易忽略掉的。具体影响的位置要根据 $01$ 段最外面的两边具体是 $0$ 还是 $1$ 进行分类讨论。找到他影响的区间后做一个区间 $\min$ 即可（因为可能之前的已经修改过去了），这部分可以用一个标记永久化的线段树实现。