https://www.acmicpc.net/problem/10942

주어진 수열이 팰린드롬인지 판별하기 위해서는 O(N)의 시간이 들고 이러한 질의가 M번 들어오기 때문에 그 때 그 떄 답을 구하려 한다면 O(NM)이 되어 시간 내에 풀 수 있음을 장담하기 힘듭니다. 대신, N이 그다지 크지 않음을 이용해 미리 S, E 범위가 팰린드롬인지 체크하는 배열 isPalindrome을 채워넣어서 해결합니다.

isPalindrome[i][j] = isPalindrome[i+1][j-1] && (num[i] == num[j]) 임을 활용하면 배열을 O(N^2)로 채울 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/10942.cpp