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 $$10^6$$). Para isso, podemos usar uma DP de intervalo. Define-se então:
$$dp[l][r] =\begin{cases} 1, & \text{se $[l, r]$ for palindromo}.\\ 0, & \text{caso contrario}. \end{cases} $$
É fácil ver que o caso base ocorre quando $$l == r$$, uma vez que toda palavra de uma unica letra forma um palíndromo. Logo:
$$dp[l][r]$$ = $$1$$, se $$(l == r)$$
A recorrência também é simples:
$$dp[l][r]$$ = ($$dp[l + 1][r – 1]$$ && $$s[l] == s[r]$$)
Uma vez que se $$[l, r]$$ é 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 $$\mathcal{O}(n^2)$$. Alem disso, podemos já responder cada pergunta em $$\mathcal{O}(n^2)$$, computando, para cada uma, o valor:
$$ \sum_{i=l}^{r}\sum_{j=l}^{r}dp[i][j] $$
Isso, porém, faz com que a complexidade de nosso algoritmo seja $$\mathcal{O}(n^2 * q)$$, 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 $$\mathcal{O}(1)$$. Assim, o problema está resolvido em $$\mathcal{O}(n^2 + q)$$, o que passa no limite de tempo.
[spoiler title=’Lembre-se: Somas Parciais collapse_link=’true’] Seja $$soma[l][r]$$ igual a soma dos valores do retângulo com vértices em $$[1][1]$$ e $$[l][r]$$. Podemos calcular esses valores com a seguinte recorrência
$$soma[l][r] = soma[l – 1][r] + soma[l][r – 1] – soma[l – 1][r – 1] + dp[l][r]$$
Além disso, a soma dos valores no quadrado com vértices $$[l, l]$$ e $$[r, r]$$ é:
$$soma[r][r] – soma[l – 1][r] – soma[r][l – 1] + soma[l – 1][l – 1]$$
[/spoiler]
Em caso de dúvidas, veja o código comentado a seguir: https://codeforces.com/contest/245/submission/212298002