先考虑简单转化一下题意。不难发现在串是 01 串的时候，任意循环移位和任意重排的效果是一样的。进一步的，只考虑所有 1 的位置时，容易发现一次操作相当于移动 1 或者 2。于是取出两边 1 的位置 $s_i$ 和 $t_i$，我们就需要找一组排列 $p$，最小化 $\sum\left\lceil\frac{|s_i-t_{p_i}|}2\right\rceil$。

先考虑如果没有上取整应该怎么做到线性。把 00 和 11 都忽略掉，10 看做 $+1$，01 看做 $-1$，做前缀和之后能够得到一个折线图（为什么匹配会想到这个？见今年 UNR D1T2）。显然对于一个查询 $[l,r]$，显然需要保证 $l-1$ 和 $r$ 的高度相同。而这中间肯定就会经过若干个高度与它们相同的点，从而将整个区间划分成若干段。显然每段的答案都是独立的，那么我们把所有的 $O(n)$ 个不同的段的答案都求出来之后对于每一个高度分别前缀和即可。

那问题就是怎么线性求出每一个段的答案。显然的，所有的段可以按照方向划分成两个集合，每个集合内部任意两个段的关系都是包含或不交，直接找出其树形结构，每个点的答案相当于把所有儿子的答案拼接起来再套一层括号，直接扫一遍树即可简单计算答案。

接下来考虑扩展到原问题。只有一对匹配的下标奇偶性不同的时候会使答案增加 $\frac 12$，所以我们需要修改匹配使得最小化 0-1 或 1-0 的匹配（下称这类匹配为不合法的）数量。先思考暴力的过程：从前往后扫，维护当前 $0$ 的左括号个数和 $1$ 的左括号个数。来一个左括号的时候就直接加进去，来右括号的时候优先匹配同种，没有同种就匹配另一种并令答案 $+1$。容易发现这是最优的。

优化肯定还是尝试继续利用刚才的那种结构。我们需要支持合并两个范围不交的匹配，头插和尾插。合并看起来就是简单的，因为两个匹配之间无法产生贡献。尾插直接用上面的方法即可。主要问题在于头插。

尝试手玩一些小数据的情况，可以发现头插的步骤大致如下：假设插入一个 0，那么找到第一对 1-0，将两个 0 连起来，于是剩下一个 1。找到下一对 0-1 的匹配连接两个 1，以此类推直到无法再找到其他的匹配。因为所有不合法匹配一定不会出现交叉，因此从前往后的顺序是唯一的，于是这个操作相当于每个连续段长度都 $-1$。

用链表维护所有的不合法匹配，把同种的匹配合并起来成为一个连续段，每次头插就遍历链表并令每个连续段长度都 $-1$，然后再删去所有空的连续段然后合并两侧。不难发现总删除次数是线性的，于是总复杂度 $O(n)$。