CF2260E.Cyclic Balance

Consider a string $t=t_1t_2\ldots t_m$ consisting of the characters 0 and 1. We call the pairs of adjacent characters of the string $t$ the pairs $t_1t_2, t_2t_3, \ldots, t_{m-1}t_m$, as well as the pair $t_mt_1$. The last pair connects the end of the string with its beginning, so exactly $m$ pairs are considered in total. If the string consists of only one character, the only pair that is considered is $t_1 t_1$.

We call a string $t$ cyclically balanced if, among its pairs of adjacent characters, the numbers of pairs 00, 01, 10, and 11 are equal.

The cost of a binary string is the minimum number of characters that need to be inserted into it so that it becomes cyclically balanced. Characters may be inserted in any positions, including before the first and after the last character of the string. It is not allowed to delete or replace the original characters.

You are given a binary string $s$ and $q$ queries. In each query, indices $l$ and $r$ are given. Find the cost of the substring $s_l s_{l+1}\ldots s_r$.

考虑一个由字符 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$ 是循环平衡的（cyclically balanced）。

一个二进制字符串的**代价（cost）**定义为：使其变为循环平衡所需插入的最少字符个数。字符可插入到任意位置（包括原字符串首字符之前和末字符之后）。不允许删除或替换原字符串中的任何字符。

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

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 3 \cdot 10^5$) — the length of the string and the number of queries.

The second line contains $s$ — a sequence of length $n$ consisting of the characters 0 and/or 1.

Then follow $q$ lines; the $i$-th of them contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the boundaries of the substring for the corresponding query.

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

第二行包含字符串 $s$ —— 一个长度为 $n$ 的、仅由字符 0 和/或 1 组成的序列。

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

Print $q$ integers: the $i$-th integer should be equal to the cost of the substring from the $i$-th query.

输出 $q$ 个整数：第 $i$ 个整数应等于第 $i$ 个查询所对应的子串的代价。

null