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

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.

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.