[AdditionalFile5223.zip](file://AdditionalFile5223.zip?type=additional_file)

#5223. 「UOI 2023 Stage 4 Day2」字符数组与近似回文

标签: 交互 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day2 T2. Масив символів і майже паліндроми

这是一个交互题。

我们称一个字符串为回文，如果它从两端读取都相同。形式上，长度为 $n$ 的字符串 $s$ 是回文，当且仅当对于 $1 \le i \le n$，$s_i = s_{n-i+1}$。例如，字符串 $\texttt{gg}, \texttt{ara}, \texttt{abacaba}, \texttt{rotator}$ 是回文，而 $\texttt{array}, \texttt{palindrome}, \texttt{uoi}$ 不是。

我们称一个字符串为近似回文，如果可以通过重新排列其字符使其成为回文。例如，字符串 $\texttt{n}, \texttt{ara}, \texttt{arr}, \texttt{array}$ 是近似回文，而 $\texttt{palindrome}, \texttt{uoi}, \texttt{random}$ 不是。

字符串的子串是通过删除其开头和结尾的某些（可能是零个）字符形成的字符串。

我们定义 $f(s)$ 为字符串 $s$ 的所有子串中，不是近似回文的最长子串的长度；如果没有这样的子串，则为 $0$。

给定一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。同时给定 $q$ 个查询，每个查询形式为 $l_i, r_i$。对于每个查询，计算 $f(s[l_i\ldots r_i])$ 的值，其中 $s[l_i\ldots r_i]$ 表示由字符 $s_{l_i}, s_{l_{i}+1}, \ldots, s_{r_i}$ 组成的子串。

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 2 \cdot 10^5)$，表示字符串的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。

第三行包含一个整数 $q$ $(1 \le q \le 2 \cdot 10^5)$，表示查询的数量。

第四行包含两个整数 $l_1, r_1$ $(1 \leq l_1 \leq r_1 \leq n)$，表示第一个查询的参数。

后续查询的参数将由评测程序提供（见「交互方式」部分）。

交互方式

评测程序将从第二个查询开始，逐行输出两个整数 $l_i, r_i$ $(1 \le l_i \le r_i \le n)$，表示当前查询的参数。

评测程序在读取到你的程序对前一个查询的回答之前，不会输出下一个查询的参数。

请确保在输出每行后调用 flush 方法。可以使用以下方式：

• C++ 中使用 fflush(stdout)、cout << endl 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 sys.stdout.flush()；
• 其他编程语言请参考相关文档。

输出格式

对于第 $i$ 个查询，单独输出一行一个整数，表示所求值 $f(s[l_i..r_i])$。

样例

输入

8
aabaaaba
3
3 7
1 8
4 4

输出

4
6
0

在第一个样例中，需要回答三个查询：

1. $s[3..7] = \texttt{baaab}$，其子串 $\texttt{aaab}$ 长度为 $4$，不是近似回文；
2. $s[1..8] = \texttt{aabaaaba}$，其子串 $\texttt{aabaaa}$ 长度为 $6$，不是近似回文；
3. $s[4..4] = \texttt{a}$，其所有子串都是近似回文。

数据范围与提示

详细子任务附加限制及分值如下表所示：