CF1672H.Zigu Zagu

You have a binary string $a$ of length $n$ consisting only of digits $0$ and $1$.

You are given $q$ queries. In the $i$-th query, you are given two indices $l$ and $r$ such that $1 \le l \le r \le n$.

Let $s=a[l,r]$. You are allowed to do the following operation on $s$:

1. Choose two indices $x$ and $y$ such that $1 \le x \le y \le |s|$. Let $t$ be the substring $t = s[x, y]$. Then for all $1 \le i \le |t| - 1$, the condition $t_i \neq t_{i+1}$ has to hold. Note that $x = y$ is always a valid substring.
2. Delete the substring $s[x, y]$ from $s$.

For each of the $q$ queries, find the minimum number of operations needed to make $s$ an empty string.

Note that for a string $s$, $s[l,r]$ denotes the subsegment $s_l,s_{l+1},\ldots,s_r$.

你有一个长度为 $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[x, y]$ 从 $s$ 中删除。

对每个查询，求出使 $s$ 变为空字符串所需的最少操作次数。

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

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

The second line contains a binary string $a$ of length $n$ ($a_i \in {0, 1}$).

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — representing the substring of each query.

第一行包含两个整数 $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$）—— 表示每次查询所对应的子串范围。

Print $q$ lines, the $i$-th line representing the minimum number of operations needed for the $i$-th query.

输出 $q$ 行，其中第 $i$ 行表示第 $i$ 个查询所需的最少操作次数。

In the first test case,

1. The substring is $\texttt{101}$, so we can do one operation to make the substring empty.
2. The substring is $\texttt{11011}$, so we can do one operation on $s[2, 4]$ to make $\texttt{11}$, then use two more operations to make the substring empty.
3. The substring is $\texttt{011}$, so we can do one operation on $s[1, 2]$ to make $\texttt{1}$, then use one more operation to make the substring empty.

在第一个测试用例中：

1. 子串为 $\texttt{101}$，因此我们可以执行一次操作使该子串变为空。
2. 子串为 $\texttt{11011}$，因此我们可以对 $s[2, 4]$ 执行一次操作得到 $\texttt{11}$，再执行两次操作使该子串变为空。
3. 子串为 $\texttt{011}$，因此我们可以对 $s[1, 2]$ 执行一次操作得到 $\texttt{1}$，再执行一次操作使该子串变为空。