Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Подпалиндромы

(Время: 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.TXTOUTPUT.TXT
18 5
aabammar
4 7
1 8
5 8
1 3
2 2
6
12
5
4
1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 A. Квадрат в треугольнике
 B. Странная последовательность
 C. Сумма простых делителей
 D. Подпалиндромы

Красноярский краевой Дворец пионеров, (c)2006 - 2023, ИНН 246305493507, E-mail: admin@acmp.ru