팰린드롬??

• 팰린드롬?에서 N의 크기가 커진 버전. 팰린드롬?에서는 O(n^2) DP로 통과가 가능했지만, 여기에서는 O(n)에 풀어야 한다.
• Manacher's algorithm을 사용해서 O(n)에 팰린드롬 반경을 모두 계산해두면, 특정 부분 문자열이 팰린드롬인지 확인하는 것은 O(1)에 가능하다. 따라서 총 시간 복잡도는 O(n+m).

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

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

Tags: [Manacher]
"""

import sys
from teflib import string


def main():
    N = int(sys.stdin.readline())
    nums = [int(x) for x in sys.stdin.readline().split()]
    modified_nums = [-1] * (N + N + 1)
    modified_nums[1::2] = nums
    radiuses = string.palindrome_radiuses(modified_nums)
    
    M = int(sys.stdin.readline())
    for _ in range(M):
        S, E = [int(x) for x in sys.stdin.readline().split()]
        center = S + E - 1
        rad = E - S        
        print('1' if rad <= radiuses[center] else '0')


if __name__ == '__main__':
    main()

• Dependency: teflib.string.palindrome_radiuses