P12571 [UOI 2023] An Array of Characters and Almost Palindromes【交互库尚未配置】

这是一道交互题。 如果一个字符串从正反两个方向读都相同，则称其为回文串。形式化地说，长度为 $n$ 的字符串 $s$ 是回文串当且仅当对所有 $1 \le i \le n$ 都有 $s_i = s_{n-i+1}$。例如，字符串 `gg`、`ara`、`abacaba` 和 `rotator` 是回文串，而 `array`、`palindrome` 和 `uoi` 不是。 我们称一个字符串为**近回文串**，如果可以通过重新排列其字符使其成为回文串。例如，字符串 `n`、`ara`、`arr` 和 `array` 是近回文串，而 `palindrome`、`uoi` 和 `random` 不是。 字符串的子串是指通过从开头和结尾删除若干（可能为零）个字符后得到的字符串。 定义 $f(s)$ 为字符串 $s$ 的所有**非**近回文串子串中的最大长度，若不存在这样的子串则返回 $0$。 给定一个由小写拉丁字母组成的长度为 $n$ 的字符串 $s$，以及 $q$ 个形如 $l_i$, $r_i$ 的查询。对于每个查询，计算 $f(s[l_i..r_i])$ 的值，其中 $s[l_i..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$）。 评测程序在读取到你的程序对前一个查询的响应后，才会输出下一个查询的参数。 请确保在每次输出后调用刷新函数。可以使用以下方法： - C++：`fflush(stdout)`、`cout

对于每个查询，输出一行一个整数——$f(s[l_i..r_i])$ 的值。

在第一个样例中，需要回答三个查询： 1. $s[3..7] =\;$`baaab`，其子串 `aaab` 长度为 4，不是**近回文串**； 2. $s[1..8] =\;$`aabaaaba`，其子串 `aabaaa` 长度为 6，不是**近回文串**； 3. $s[4..4] =\;$`a`，其所有子串都是**近回文串**。 ### 评分标准 - （$6$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n$ 为偶数，$s$ 形如 `aabbaabbaa...`； - （$9$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n \le 200$； - （$5$ 分）：$q=1$，$l_1=1$，$r_1=n$，$n \le 5000$； - （$8$ 分）：$q=1$，$l_1=1$，$r_1=n$； - （$10$ 分）：$s$ 仅包含字母 `a` 和 `b`； - （$8$ 分）：对所有 $1 \le i \le q$，$s_{l_i} \neq s_{r_i}$； - （$7$ 分）：对所有 $1 \le i < n$，$s_i \neq s_{i+1}$； - （$10$ 分）：$s$ 仅包含字母 `a`、`b`、`c`、`d`、`e` 和 `f`； - （$18$ 分）：对所有 $1 \le i \le q$，$(r_i-l_i+1)$ 为奇数； - （$19$ 分）：无额外限制。 翻译由 DeepSeek V3 完成