← 返回题目列表

Codeforces · 1672/H

H. 紫谷扎古

中文机器翻译题面 查看原题

您有一个长度为 $$$n$$$ 的二进制字符串 $$$a$$$,仅由数字 $$$0$$$ 和 $$$1$$$ 组成。

您收到 $$$q$$$ 查询。在第 $$$i$$$ 查询中,为您提供两个索引 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$。

设$$$s=a[l,r]$$$。您可以对$$$s$$$进行以下操作:

1. 选择两个索引 $$$x$$$ 和 $$$y$$$,使得 $$$1 \le x \le y \le |s|$$$。设 $$$t$$$ 为子串 $$$t = s[x, y]$$$。然后对于所有 $$$1 \le i \le |t| - 1$$$,条件 $$$t_i \neq t_{i+1}$$$ 必须成立。请注意,$$$x = y$$$ 始终是有效的子字符串。
2. 从$$$s$$$中删除子字符串$$$s[x, y]$$$。

对于每个 $$$q$$$ 查询,找到使 $$$s$$$ 成为空字符串所需的最少操作数。

请注意,对于字符串 $$$s$$$,$$$s[l,r]$$$ 表示子段 $$$s_l,s_{l+1},\ldots,s_r$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10 ^ 5$$$) — 分别是二进制字符串 $$$a$$$ 的长度和查询次数。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$a$$$ ($$$a_i \in \{0, 1\}$$$)。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 表示每个查询的子字符串。

输出

打印 $$$q$$$ 行,第 $$$i$$$ 行表示第 $$$i$$$ 查询所需的最少操作数。

示例

输入 #1

5 3
11011
2 4
1 5
3 5

输出 #1

1
3
2

输入 #2

10 3
1001110110
1 10
2 5
5 10

输出 #2

4
2
3

注意

在第一个测试用例中,

1. 子串是$$$\texttt{101}$$$,所以我们可以通过一次操作将子串清空。
2. 子串是 $$$\texttt{11011}$$$,所以我们可以对 $$$s[2, 4]$$$ 进行一次操作,将 $$$\texttt{11}$$$ 变为空,然后再使用两次操作将子串清空。
3. 子串是 $$$\texttt{011}$$$,所以我们可以对 $$$s[1, 2]$$$ 进行一次操作,将 $$$\texttt{1}$$$ 变为空,然后再进行一次操作,将子串清空。