| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 7 | 3 | 3 | 42.857% |
Макс и Дюк попали на мясокомбинат и нашли длинную-предлинную цепочку сосисок, которую можно представить как строку $s,ドル каждой сосиске соответствует маленькая латинская буква.
Они считают отрезок сосисок $[a, b]$ вкусным, если непрерывная последовательность сосисок с $a$ по $b$ совпадает с этой же последовательностью в перевернутом виде. В каждый момент Макс наблюдает за отрезком сосисок $[l, r]$ и задает Дюку странные запросы: сколько вкусных подотрезков видит Макс.
Вам необходимо узнать количество пар $a$ и $b$ таких, что $l \le a \le b \le r$ и отрезок $[a, b]$ вкусный.
В первой строке задано число $n$ и $m$ --- длина строки $s$ и количество запросов (1ドル \le n,m \le 500,000円$).
Во второй строке задана последовательность маленьких латинских букв длины $n$ --- строка $s$.
Далее следует $m$ строк. В каждой записаны числа $l$ и $r$ --- границы i-го запроса (1ドル \le l \le r \le n$).
Для каждого запроса выведите количество вкусных подотрезков.
8 5 oobokkor 1 3 1 8 2 2 4 7 5 8
4 12 1 6 5