CF1672H Zigu Zagu

你有一个长度为 $n$ 的二进制串 $a$。 现在给出 $q$ 次询问，每次询问给出两个数 $l,r$，保证 $1 \leq l \leq r \leq n$。 令 $s=a[l,r]$，你可以对 $s$ 做如下操作： 1.选择两个数 $x,y$，满足 $1 \leq x \leq y \leq |s|$。令子串 $t=s[x,y]$，对于所有的 $1 \leq i \leq |t|-1$，需要满足 $t_i \neq t_{i+1}$，操作才是合法的，否则是不合法的。注意 $x=y$ 时永远是合法的。 2.从 $s$ 中删除 $s[x,y]$。 对于每一个询问，请求出最少需要多少个操作才能把 $s$ 变成一个空串。 标记提示：$s[l,r]$ 表示从 $l$ 开始，到 $r$ 结束的子串。

第一行输入两个正整数 $n,q$ $(1\leq n,q \leq 2\times 10^5)$。 第二行，输入二进制串 $a$。 接下来的 $q$ 行，每行两个整数 $l,r$ 。

对于每一个询问，输出一个正整数表示结果。

在第一个测试用例中， 1. 子串为 $\texttt{101}$，因此我们可以通过一次操作使其变为空。 2. 子串为 $\texttt{11011}$，我们可以对 $s[2, 4]$ 进行一次操作得到 $\texttt{11}$，再通过两次操作使其变为空。 3. 子串为 $\texttt{011}$，我们可以对 $s[1, 2]$ 进行一次操作得到 $\texttt{1}$，再通过一次操作使其变为空。