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

    ID: 14138 远端评测题 4000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2023交互题Special JudgeUOI(乌克兰)

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

题目描述

This is an interactive problem.

A string is considered a palindrome if it reads the same from both sides. Formally, a string ss of length nn is considered a palindrome if si=sni+1s_i = s_{n-i+1} for 1in1 \le i \le n. For example, the strings gg, ara, abacaba, and rotator are palindromes, while the strings array, palindrome, and uoi are not.

We call a string a nearly palindrome if its characters can be rearranged to form a palindrome. For example, the strings n, ara, arr, and array are nearly palindromes, while the strings palindrome, uoi, and random are not.

A substring of a string is a string that can be obtained by deleting some (possibly zero) elements from its beginning and end.

Let f(s)f(s) be the maximum length among the lengths of substrings of ss that are not nearly palindromes, or 00 if there are no such substrings.

You are given a string ss of length nn consisting of lowercase Latin letters. You are also given qq queries of the form lil_i, rir_i. For each query, find the value of f(s[li..ri])f(s[l_i..r_i]), where s[li..ri]s[l_i..r_i] denotes the substring consisting of characters sli,sli+1,,sris_{l_i}, s_{l_{i} + 1}, \ldots, s_{r_i}.

输入格式

The first line contains one integer nn (1n21051 \le n \le 2\cdot 10^5) --- the length of the string.

The second line contains a string ss consisting of nn lowercase Latin letters.

The third line contains one integer qq (1q21051\le q \le 2\cdot 10^5) --- the number of queries.

The fourth line contains two integers l1,r1l_1, r_1 (1l1r1n1 \leq l_1 \leq r_1 \leq n) --- the parameters of the first query.

You will receive the parameters of the next queries from the jury program (see section Interaction Protocol).

Interaction Protocol

The jury program will output two integers lil_i, rir_i (1lirin1\le l_i\le r_i\le n) on separate lines for each query, starting from the second one.

The jury program will not output the parameters for the next query until it reads the response of your program to the previous query.

Make sure to call the flush\texttt{flush} method after outputting each line. You can use:

  • fflush(stdout)\texttt{fflush(stdout)}, cout << endl\texttt{cout <{}< endl}, or cout.flush()\texttt{cout.flush()} in C++\tt{C++};
  • System.out.flush()\texttt{System.out.flush()} in Java\tt{Java};
  • flush(output)\texttt{flush(output)} in Pascal\tt{Pascal};
  • sys.stdout.flush()\texttt{sys.stdout.flush()} in Python\tt{Python};
  • consult the documentation for other programming languages.

输出格式

For each ii-th query, output one integer --- the value of f(s[li..ri])f(s[l_i..r_i]), in a separate line.

8
aabaaaba
3
3 7
1 8
4 4
4
6
0

提示

In the first example, you need to find the answers to three queries:

  • s[3..7]=  s[3..7] =\;baaab, which has a substring aaab of length 4, which is not an almost palindrome;
  • s[1..8]=  s[1..8] =\;aabaaaba, which has a substring aabaaa of length 6, which is not an almost palindrome;
  • s[4..4]=  s[4..4] =\;a, all substrings of which are almost palindromes.

Scoring

  • (66 points): q=1q=1, l1=1l_1=1, r1=nr_1=n, nn is even, ss has the form aabbaabbaa...;
  • (99 points): q=1q=1, l1=1l_1=1, r1=nr_1=n, n200n \le 200;
  • (55 points): q=1q=1, l1=1l_1=1, r1=nr_1=n, n5000n \le 5000;
  • (88 points): q=1q=1, l1=1l_1=1, r1=nr_1=n;
  • (1010 points): ss contains only letters a\tt{a} and b\tt{b};
  • (88 points): slisris_{l_i} \neq s_{r_i} for 1iq1 \le i \le q;
  • (77 points): sisi+1s_i \neq s_{i+1} for 1i<n1 \le i < n;
  • (1010 points): ss contains only letters a,b,c,d,e\tt{a}, \tt{b}, \tt{c}, \tt{d}, \tt{e}, and f\tt{f};
  • (1818 points): (rili+1)(r_i-l_i+1) is odd for 1iq1\le i\le q;
  • (1919 points): without additional constraints.