观察：每次交换最左边的相邻逆序对，即插入排序，得到的就是最优解。

证明：设第 $i$ 个数左边比它大数的个数是 $c$，最终位置是 $j$，则它至少需要向左移动 $c$ 步，向右移动 $j-i+c$ 步，而插入排序一定是先左移再右移，是代价最小的。因此每个数的移动代价之和也是最小的。

上述的代价还可以用以下式子计算： $$ {n+1\choose 3}-\sum_{i=1}^n{c_i+1\choose 2} $$ 其中 $c_i$ 是第 $i$ 个数之前小于等于它的数的个数。可以考虑每个数先向左再向右，向左最终的位置就是 $c_i$，所以省掉了左边的部分。

因为值域（字符集）很小，用线段树维护区间中每个数的出现次数，出现次数前缀和，以及对于每个 $x$，所有满足 $s_i=x$ 的位置的 $c_i$ 和 ${c_i\choose 2}$ 之和，就可以在 $O(|\Sigma|)$ 的时间内合并。

对于修改操作 3，只需要打标记表示将区间依次赋值为 $a_1$ 个 $\tt A$，$a_2$ 个 $\tt B$，以此类推。打标记时也可以在 $O(|\Sigma|)$ 的时间内更新维护的信息。

总时间复杂度 $O((n+q\log n)|\Sigma|)$。