← 返回题目列表

AtCoder · abc381_e

H. 11/22 子序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

本题中 11/22 字符串的定义与问题 A 和 C 相同。

一个字符串 T 被称为 11/22 字符串 当满足以下所有条件时:

  • |T| 是奇数。在这里, |T| 表示长度 T.
  • 的 1-st 通过 (\frac{|T|+1}{2} - 1)第个字符全部 1.
  • 的 (\frac{|T|+1}{2})- 第一个字符是 /.
  • 的 (\frac{|T|+1}{2} + 1)-th 通过 |T|第个字符全部 2.

例如, 11/22, 111/222,和 / 是 11/22 字符串,但是 1122, 1/22, 11/2222, 22/11,和 //2/2/211 不是。

给定一个字符串 S 长度 N 组成 1, 2,和 /,过程 Q 查询。

每个查询提供两个整数 L 和 R。让 T 是 (连续) 的子串 S 来自 L-th 通过 R- 第一个字符。求子序列的最大长度 (不一定连续) of T 这是一个 11/22 字符串。如果不存在这样的子序列,则打印 0.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S 是一个长度为 N 组成 1, 2,和 /.
  • 1 \leq L \leq R \leq N
  • N, Q, L,和 R 是整数。

输入

输入由标准输入按以下格式给出。在这里, \mathrm{query}_i 表示 i- 第一个查询。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

L R

输出

打印 您选择的 Q 行。的 i- 第行应包含以下问题的答案 i- 第一个查询。


示例输入 1

12 5
111/212/1122
1 7
9 12
3 6
4 10
1 12

示例输出 1

5
0
3
1
7

对于第一个查询,来自 1-st 至 7- 第一个字符 S is 111/212。该字符串包含 11/22 作为子序列,它是 11/22 字符串的最长子序列。因此,答案是 5.
对于第二个查询,来自 9-th 至 12- 第一个字符 S is 1122。该字符串不包含任何 11/22 字符串的子序列,因此答案是 0.