Для каждой позиции найдем максимальный палиндром из нее. Для этого переберем позицию и сделаем бинарный поиск по длине палиндрома, проверим равенство подстрок хешами. Пусть S[i] — максимальный палиндром с центром i
Решим задачу отдельно для и
. На таких отрезках однозначно задается граница, которая мешает расширяться палиндромам. Теперь решаем оффлайн сканлайн + ДО для ответа на запрос.
Для отрезков нужно узнать сколько чисел от меньше чем l. Так же сумму всех чисел, которые больше, либо равны l.
Нам нужно посчитать сумму i - max(S[i], l) по всем i в отрезке . Раскроем max(S[i], l) и представим его, как сумму чисел, которые меньше l прибавить количество чисел, которые больше либо равны l умноженных на l
Развернем строк и аналогично решаем для .