分数: 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.