题目描述

难度分:$2700$

输入$n(1 \leq n \leq 2 \times 10^5)$，$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的01字符串$s$。

定义交替字符串为相邻字符互不相同的字符串。定义$f(t)$为，不断删除字符串$t$中的交替子串，使得$t$为空的最小操作次数。

例如11011$\rightarrow($删除101$)\rightarrow$11 -> 1$\rightarrow$空串，所以$f($11011$)=3$。

输入$q$个询问，每个询问输入$L$，$R(1 \leq L \leq R \leq n)$。

对于每个询问，输出$s$的子串$[L,R]$的$f$值。

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

算法

贪心构造+前缀和

根据题意，相邻相同的字符个数，会影响答案。

比如11需要操作$2$次。

11...11需要操作$3$次。省略号表示相邻不同的子串，因为11011、1101011、110101011等没有本质区别，用省略号表示，这样我们更能看出问题的本质。

11...11...11需要操作$4$次。那么11...11...11...00需要操作几次？

答案仍然是4次，因为我们可以先删除1...0，得到11...11...10，这样最后的$0$可以和最后一个$1$一起移除掉，变为11...1，最后两次分别移除后缀1...1以及开头的1。

同理11...11...11...00...00仍然是$4$次，第$1$次干掉11...11...1[1...0]0...00变为11...11...10...00，第$2$次干掉11...1[1...10]...00变为11...1...00，第$3$次干掉1[1...1...0]0变为10，最后把10干掉即可。但如果00比11多，答案就以00的个数为主了。

一般地，把11和00视作【左右括号】，或者【右左括号】，问题类似括号匹配。

如果11比00多，那么00都可以免费移除掉，答案是11的个数加一。否则答案是00的个数加一。用前缀和数组$zero$和$one$统计00和11的个数，便可快速回答询问。

复杂度分析

时间复杂度

预处理出00和11的前缀和只需要遍历一遍字符串$s$，时间复杂度为$O(n)$。后面的每条询问都是$O(1)$的，因此整个算法的时间复杂度为$O(n+q)$。

空间复杂度

空间消耗的瓶颈就是两个前缀和数组$one$和$zero$，空间都是线性的，为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
char s[N];
int n, q, one[N], zero[N];

int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    for(int i = 2; i <= n; i++) {
        if(s[i] == '1' && s[i - 1] == '1') {
            one[i] = one[i - 1] + 1;
        }else {
            one[i] = one[i - 1];
        }
        if(s[i] == '0' && s[i - 1] == '0') {
            zero[i] = zero[i - 1] + 1;
        }else {
            zero[i] = zero[i - 1];
        }
    }
    while(q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int o = one[r] - one[l], z = zero[r] - zero[l];
        printf("%d\n", max(o, z) + 1);
    }
    return 0;
}