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$($\leq n,q \leq 2\times 10^5$)。 第二行，输入二进制串$a$。 接下来的$q$行，每行两个整数$l,r$。 **输出格式** 对于每一个询问，输出一个正整数表示结果。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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.