AT_abc381_e [ABC381E] 11/22 Subsequence

在本题中，11/22 字符串的定义与 A 问题和 C 问题相同。 当字符串 $T$ 满足以下所有条件时，称 $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$，请你求出 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的**连续**子串中，作为 $T$ 时，11/22 字符串的**（不要求连续的）**子序列的最大长度。若不存在这样的子序列，则输出 $0$。

输入以如下格式从标准输入读入。这里 $\mathrm{query}_i$ 表示第 $i$ 个查询。 > $N$ $Q$ > $S$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个查询的格式如下： > $L$ $R$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

### 约束 - $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$ 均为整数 ### 样例解释 1 对于第 $1$ 个查询，$S$ 的第 $1$ 个字符到第 $7$ 个字符组成的子串为 `111/212`。该字符串包含 `11/22` 作为子序列，这是 11/22 字符串中长度最大的。因此答案为 $5$。对于第 $2$ 个查询，$S$ 的第 $9$ 个字符到第 $12$ 个字符组成的子串为 `1122`。该字符串不包含任何 11/22 字符串作为子序列，因此答案为 $0$。 由 ChatGPT 4.1 翻译