Макс и Дюк

Для каждой позиции найдем максимальный палиндром из нее. Для этого переберем позицию и сделаем бинарный поиск по длине палиндрома, проверим равенство подстрок хешами. Пусть S[i] — максимальный палиндром с центром i

Решим задачу отдельно для и . На таких отрезках однозначно задается граница, которая мешает расширяться палиндромам. Теперь решаем оффлайн сканлайн + ДО для ответа на запрос.

Для отрезков нужно узнать сколько чисел от меньше чем l. Так же сумму всех чисел, которые больше, либо равны l.

Нам нужно посчитать сумму i - max(S[i], l) по всем i в отрезке . Раскроем max(S[i], l) и представим его, как сумму чисел, которые меньше l прибавить количество чисел, которые больше либо равны l умноженных на l

Развернем строк и аналогично решаем для .