103814: [Atcoder]ABC381 E - 11/22 Subsequence

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and C.

A string $T$ is called an 11/22 string when it satisfies all of the following conditions:

• $|T|$ is odd. Here, $|T|$ denotes the length of $T$.
• The $1$-st through $(\frac{|T|+1}{2} - 1)$-th characters are all 1.
• The $(\frac{|T|+1}{2})$-th character is /.
• The $(\frac{|T|+1}{2} + 1)$-th through $|T|$-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

Given a string $S$ of length $N$ consisting of 1, 2, and /, process $Q$ queries.

Each query provides two integers $L$ and $R$. Let $T$ be the (contiguous) substring of $S$ from the $L$-th through $R$-th character. Find the maximum length of a subsequence (not necessarily contiguous) of $T$ that is an 11/22 string. If no such subsequence exists, print 0.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ is a string of length $N$ consisting of 1, 2, and /.
• $1 \leq L \leq R \leq N$
• $N$, $Q$, $L$, and $R$ are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{query}_i$ denotes the $i$-th query.

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

Each query is given in the following format:

$L$ $R$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 1

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

Sample Output 1

5
0
3
1
7

For the first query, the substring from the $1$-st to $7$-th character of $S$ is 111/212. This string contains 11/22 as a subsequence, which is the longest subsequence that is an 11/22 string. Therefore, the answer is $5$.
For the second query, the substring from the $9$-th to $12$-th character of $S$ is 1122. This string does not contain any subsequence that is an 11/22 string, so the answer is $0$.

问题陈述

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

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

• $|T|$是奇数。这里，$|T|$表示$T$的长度。
• 第1个到$(\frac{|T|+1}{2} - 1)$个字符全部是1。
• 第$(\frac{|T|+1}{2})$个字符是/。
• 第$(\frac{|T|+1}{2} + 1)$个到$|T|$个字符全部是2。

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

给定一个由1、2和/组成的长度为$N$的字符串$S$，处理$Q$个查询。

每个查询提供两个整数$L$和$R$。令$T$为$S$中从第$L$个到第$R$个字符的（连续的）子字符串。找出$T$的一个子序列（不一定是连续的），该子序列是11/22字符串的最大长度。如果不存在这样的子序列，则打印0。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$是由1、2和/组成的长度为$N$的字符串。
• $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

对于第一个查询，$S$的第1个到第7个字符的子字符串是111/212。这个字符串包含11/22作为子序列，这是最长的11/22字符串。因此，答案是$5$。
对于第二个查询，$S$的第9个到第12个字符的子字符串是1122。这个字符串不包含任何是11/22字符串的子序列，所以答案是$0$。