题解

给定一个长度为 $n$ 的序列 $s$ （仅包含字符 '0' 和 '1'），我们可以对任意子串执行以下操作：每次添加或删除一个符号（可以是 '0' 或 '1'）需要付出 1 点代价；此外，可以无代价地交换任意相邻符号。现在要求我们求出所有非空子串的"规整代价"之和。

一个子串 $t$ 的规整代价定义为：通过任意次数交换相邻符号的前提下，确保任意相邻的符号都不相等的最少添加或删除操作次数。换句话说，最小的操作次数就是将该子串变为一个 "交替字符串"（例如 '010101' 或 '101010'）所需的操作。

题目内容

小蓝在整理一串由 ‘0’ 和 ‘1’ 组成的数据序列。她可以无代价地交换任意两个相邻符号的位置。此外，她每次可以添加或删除一个符号（可以是 ‘0’ 或 ‘1’），每次操作需要付出 1 点代价。

她希望最终序列中任意相邻的两个符号都不相同。对于给定的初始序列，定义其 规整代价 为通过上述操作达成目标所需的最小代价。

现在给定一个长度为 $n$ 的序列，请你计算该序列所有非空连续子串的规整代价之和。

约束条件