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

N/A

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.