UwU

Жаль блог о контесте набрал минусовой вклад

F2 странные ограничения. Приведу свое решение, которое вроде зашло, но ИМХО легче:

Найдем длину максимального палиндрома, предварительно насчитав dp[l][r] — длина макс.палиндрома на промежутке $$$[l;r]$$$. Теперь найдем ответ для минимума за $$$O(n^2*c)$$$ (для максимума похожий алгоритм). Будем поддерживать $$$[ans_l;ans_r]$$$ и еще сколько нам осталось найти букв палиндрома ($$$len$$$), зная что ответ хранится в нем. Если $$$len = 0$$$ можно выйти из алгоритма. Будем перебирать буквы по возрастанию, так как нам нужно найти минимальный лексикографически палиндром. Если кол-во вхождений буквы меньше 2-х, то перебираем дальше. Иначе найдем самое левое и самое правое вхождение этой буквы, обозначим за $$$l_c$$$ и $$$r_c$$$. Если $$$dp[l_c][r_c] \lt len$$$, то также скипаем. Иначе обновляем $$$l:=l_c+1$$$, $$$r:=r_c-1$$$, $$$len:=len-2;$$$.

И еще немного обработки случаев для палиндромов нечетной длины.

посылка.

код еще оптимайзить и оптимайзить.

UPD: если предподсчитать за $$$O(c*n)$$$ $$$next_c[i]$$$ и $$$last_c[i]$$$, которые показывают ближайшую следующую/предыдущую соответсвенно позицию буквы $$$c$$$, асимптотика непосредственного вычисления ответа снижается до $$$O(n*c)$$$, и у нас остается только динамика за квадрат, которая на самом деле не 10^4 * 10^4 = 10^8, а 10^4 * (10^4 -1)/2 ~= 5*10^7 операций, т.к. это заходит за 500мс, много вопросов к тестам. А так идея контеста интересна

Я туплю немного

А такая нечитаемость условий задумывалась?

не дерево фенрика, а дерево фенвика)