循环平衡字符串

题目描述

考虑一个由字符 0 和 1 组成的字符串 $t=t_1t_2\ldots t_m$。我们称字符串 $t$ 的相邻字符对为 $t_1t_2, t_2t_3, \ldots, t_{m-1}t_m$，以及 $t_mt_1$。最后一对将字符串末尾与开头相连，因此总共恰好考虑 $m$ 对。如果字符串只包含一个字符，则只考虑 $t_1t_1$ 这一对。

我们称字符串 $t$ 是循环平衡的，如果在其相邻字符对中，00、01、10、11 的数量相等。

一个二进制字符串的代价为使其变为循环平衡所需插入的最少字符数。字符可以插入在任意位置，包括第一个字符之前和最后一个字符之后。不允许删除或替换原有字符。

给定一个二进制字符串 $s$ 和 $q$ 个查询。每个查询给定下标 $l$ 和 $r$，求子串 $s_l s_{l+1}\ldots s_r$ 的代价。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$），分别表示字符串长度和查询次数。

第二行包含字符串 $s$，长度为 $n$，由字符 0 和/或 1 组成。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示对应查询的子串边界。

输出格式

输出 $q$ 个整数，第 $i$ 个整数表示第 $i$ 个查询的子串代价。

样例输入

11 7
00111100000
1 8
1 1
1 2
1 4
3 6
2 7
7 11

样例输出

4
3
2
0
4
2
7

样例解释

对于第一个查询 $l=1, r=8$，子串为 00111100。按循环顺序写出相邻字符对：

00、01、11、11、11、10、00、00

统计得到 00 有 $3$ 个，01 有 $1$ 个，10 有 $1$ 个，11 有 $3$ 个。四类数量不相等，因此原串不平衡。

为了使字符串达到循环平衡，最终长度必须是 $4$ 的倍数，并且每类相邻字符对的数量都等于最终长度的四分之一。当前长度为 $8$。如果保持长度 $8$，则每类需要 $2$ 对，但 00 和 11 已经各有 $3$ 对，所以不可行。将长度增加到 $12$ 需要插入 $4$ 个字符。例如可以在原串的第二个 1 后插入 00，在末尾后插入 11，得到 001100110011，该串中 00、01、10、11 的数量均为 $3$，满足循环平衡。因此最少需要插入 $4$ 个字符，代价为 $4$。

数据范围

• $1 \le n, q \le 3 \times 10^5$
• $1 \le l_i \le r_i \le n$
• 字符串 $s$ 长度为 $n$，仅包含字符 0 和 1。