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$结束的子串。

无

无

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.