Frequent values

• 화려한 마을2과 기본적으로는 동일한 문제이다. 풀이는 그쪽을 참고.
• 차이점은 이 문제에서는 한 입력에 여러개의 테스트 케이스가 들어올 수 있다는 것, 그런데 제한시간은 오히려 더 짧다. 아마도 최적 솔루션 대신 Mo's algorithm을 사용하려 하면 Python에서는 해보지는 않았지만 시간 초과가 날거 같다. (cpp로는 최적화를 잘 하면 여전히 mo's algorithm으로 통과된다는 듯 하다)

"""Solution code for "BOJ 6515. Frequent values".

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

import bisect
import itertools
import sys
from teflib import segmenttree


def solve():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    brightness = [int(x) for x in sys.stdin.readline().split()]
    occurrences = [len(list(g)) for _, g in itertools.groupby(brightness)]
    segtree = segmenttree.SegmentTree(occurrences, merge=max)
    pos = 0
    end_pos = [(pos := pos + x) for x in occurrences]
    for _ in range(Q):
        X, Y = [int(x) for x in sys.stdin.readline().split()]
        l, r = X - 1, Y - 1
        if brightness[l] == brightness[r]:
            print(r - l + 1)
        else:
            left_group = bisect.bisect_left(end_pos, l)
            right_group = bisect.bisect_right(end_pos, r)
            answer = max(end_pos[left_group] - l,
                         r - end_pos[right_group - 1] + 1)
            if left_group + 1 < right_group:
                answer = max(answer, segtree.query(left_group + 1, right_group))
            print(answer)

            
def main():
    while True:
        try:
            solve()
        except ValueError:
            break


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree