팰린드롬?

• S부터 E까지의 부분문자열이 팰린드롬인지 여부를 저장하는 테이블 dp[S][E]는 2차원 DP를 통해서 O(n^2)에 쉽게 구할수 있다. 이 테이블을 이용하면 각각의 쿼리를 O(1)에 처리할 수 있으므로, 이 방법으로는 총 시간복잡도가 O(n^2+m)이 된다.
• S부터 E까지의 부분문자열이 팰린드롬인지 여부를 저장하는 대신, C번째 문자를 중심으로 하는 팰린드롬 중 가장 큰 것의 길이를 저장하는 리스트 dp2[C]를 계산해 둘수도 있다. 이 값들을 갖고도 각각의 쿼리를 역시 O(1)에 처리할수 있다. 그리고 이 값들은 1차원 리스트이므로 공간복잡도가 O(n^2)이 아니라 O(n)이라는 장점이 있다. 나도 이 방법을 사용했다.
• dp2[C]도 간단한 DP를 통해서 O(n^2) 시간에 계산이 가능하다. 다만 짝수길이 팰린드롬은 중심에 해당하는 문자가 없으므로, 따로 처리가 필요하다. 첨부한 코드에서는 홀수 길이 팰린드롬을 위한 배열과, 짝수 길이 팰린드롬을 위한 배열을 따로 나눠서 계산했다.
• Manacher's algorithm을 사용하면 여기서의 dp2배열을 O(n^2)이 아닌 O(n)에 구할 수 있다. 이 알고리즘을 써서 같은 문제를 푸는 코드는 팰린드롬??을 참고.

"""Solution code for "BOJ 10942. 팰린드롬?".

- Problem link: https://www.acmicpc.net/problem/10942
- Solution link: http://www.teferi.net/ps/problems/boj/10942
"""

import sys


def main():
    N = int(sys.stdin.readline())
    nums = [int(x) for x in sys.stdin.readline().split()]

    max_odd_lengths = []
    for i in range(N):
        max_len = -1
        for l, r in zip(nums[i:], reversed(nums[:i + 1])):
            if l != r:
                break
            max_len += 2
        max_odd_lengths.append(max_len)
        
    max_even_lengths = []
    for i in range(N - 1):
        max_len = 0
        for l, r in zip(nums[i + 1:], reversed(nums[:i + 1])):
            if l != r:
                break
            max_len += 2
        max_even_lengths.append(max_len)

    M = int(sys.stdin.readline())
    for _ in range(M):
        S, E = [int(x) for x in sys.stdin.readline().split()]
        length = E - S + 1
        max_length = (max_odd_lengths[(S + E) // 2 - 1] if length % 2
                      else max_even_lengths[(S + E) // 2 - 1])
        print('1' if length <= max_length else '0')


if __name__ == '__main__':
    main()