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