Solução escrita por Henrique Vianna
Conhecimento prévio necessário:
Uma ideia inicial é pré-calcular os intervalos que formam palíndromos para que, de alguma forma, seja possível responder queries de forma rápida (perceba que Q pode chegar a ). Para isso, podemos usar uma DP de intervalo. Define-se então:
É fácil ver que o caso base ocorre quando , uma vez que toda palavra de uma unica letra forma um palíndromo. Logo:
= , se
A recorrência também é simples:
= ( && )
Uma vez que se é palíndromo, então seus extremos devem ter o mesmo carácter e a palavra formada pelo restante deve ser também um palíndromo. Sendo assim, sabemos para todos os intervalos se ele é palíndromo ou não, calculando isso com uma complexidade de . Alem disso, podemos já responder cada pergunta em , computando, para cada uma, o valor:
Isso, porém, faz com que a complexidade de nosso algoritmo seja , o que é lento demais para os limites do problema.
Entretanto, percebe-se que essa expressão corresponde ao somatório dos valores de um quadrado da matriz da nossa DP. Podemos, então, calcular somas parciais 2D da DP e utilizá-las para rapidamente calcular a soma e responder a cada pergunta em . Assim, o problema está resolvido em , o que passa no limite de tempo.
Seja igual a soma dos valores do retângulo com vértices em e . Podemos calcular esses valores com a seguinte recorrência
Além disso, a soma dos valores no quadrado com vértices e é:
Em caso de dúvidas, veja o código comentado a seguir: https://codeforces.com/contest/245/submission/212298002