首页 > 试题广场 >

选数Ⅱ

[编程题]选数Ⅱ
  • 热度指数：490 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

一个长度为  的只包含字符  和  的字符串 ，下标从  开始。

每次给出一个区间 ，对下标在区间内（包含左右端点）的字符进行染色，在满足下面两个要求的前提下，最多能染色多少个字符？注意每个询问都是独立的，不会对后续询问造成影响。

1）染色的字符的下标  满足 l\leq p_i\leq r。

2）不存在任意两个相邻的字符  同时被染色。


输入描述:
第一行包含两个整数 n\ q\ (1\leq n,q\leq 3\times10^5)，表示字符串长度和询问次数。
第二行包含一个长度为  且只包含数字  和  的字符串。
接下来  行，每行两个整数 l\ r\ (1\leq l\leq r\leq n)，表示询问区间。


输出描述:
输出包含  行，每行一个整数，表示最多染色的下标。
示例1

输入

8 2
01011111
2 5
1 8

输出

3
6

说明

第一个询问染色下标  或 。
第二个询问染色下标 。

备注:

算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

线段树 动态规划
难度：
0条回答 112浏览

热门推荐

相关试题

选数Ⅱ

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号