CF2260E Cyclic Balance

给定一个仅由字符 0 和 1 组成的字符串 $t = t_1 t_2 \ldots t_m$。我们称字符串 $t$ 的相邻字符对为 $t_1 t_2, t_2 t_3, \ldots, t_{m-1} t_m$，以及 $t_m t_1$ 这一对。最后一对将字符串的结尾与开头相连，因此总共会考虑恰好 $m$ 对字符。如果字符串仅有一个字符，则唯一考虑的字符对为 $t_1 t_1$。 若一个字符串 $t$ 的所有相邻字符对中，00、01、10、11 四种对的数量均相等，则称 $t$ 是“循环平衡”的。 一个二进制字符串的“代价”定义为必须插入的最少字符数，使得它变为循环平衡。可以在任意位置插入字符，包括在原字符串前或后，但不允许删除或替换原有字符。 现给定一个二进制字符串 $s$，以及 $q$ 次询问。每次询问给定下标 $l$ 和 $r$，请计算子串 $s_l s_{l+1} \ldots s_r$ 的代价。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$）——字符串长度和询问次数。 第二行包含长度为 $n$ 的字符串 $s$，仅由字符 0 和/或 1 组成。 接下来 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示每次询问的子串区间。

输出 $q$ 个整数，第 $i$ 个整数表示第 $i$ 次询问中，对应子串的代价。

由 ChatGPT 5 翻译