Подпалиндромы
(Время: 8 сек. Память: 512 Мб Сложность: 88%)
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки «abba» и «ata» являются палиндромами.
Подстрокой некоторой строки называется непустая последовательность подряд идущих символов в исходной строке.
Подпалиндромом назовем подстроку некоторой строки, которая является палиндромом.
Дана строка s. Требуется отвечать на запросы вида: сколько всего подпалиндромов на подстроке отрезка [l,r] строки s.
Входные данные
В первой строке входного файла INPUT.TXT заданы числа n и q – длина строки s и количество запросов (1 ≤ n, q ≤ 5×105). Во второй строке задана последовательность строчных английских букв длины n – строка s. Далее идут q строк, в каждой из которых записаны числа l и r, определяющие подстроку запроса ( 1 ≤ l ≤ r ≤ n).
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса в отдельной строке выведите количество подпалиндромов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 5
aabammar
4 7
1 8
5 8
1 3
2 2
| 6
12
5
4
1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
