화려한 마을2

• Frequent values와 같은 문제.
• 구간 mode 쿼리인 것 처럼 보이지만, 밝기값들이 정렬되어 있다는 조건이 있기 때문에 더 쉽게 풀수 있다.
  • 꼭 정렬되어있지 않더라도, 같은 값들이 인접하게 배치되도록 그룹핑되어 있다면 같은 방법으로 풀 수 있다.
• 간단하게 짜는 방법은 세그먼트 트리로 분할 정복을 이용하는 방법.
  • 각 구간에 해당하는 노드를, 아래의 5가지 값을 갖도록 만든다
    • l_val : 구간의 왼쪽 끝 원소의 값
    • r_val : 구간의 오른쪽 끝 원소의 값
    • l_count : 구간에서 l_val의 갯수
    • r_count : 구간에서 r_val의 갯수
    • max_count : 구간에서 가장 많은 값의 갯수
  • 이 값들을 이용하면, 구간 l과 r이 합쳐진 구간에 대한 값들도 O(1)에 계산할 수 있다.
  • 따라서 이렇게 만든 세그먼트 트리는 한개의 쿼리를 O(logn)에 처리 가능하다.
  • 세그먼트 트리를 만드는데에 O(n), m개의 쿼리를 처리하는 데에 O(mlogn). 총 시간 복잡도는 O(n+mlogn)
• 윗 방법이 깔끔하게 구현되기는 하지만, 좀더 효율적으로 동작하는 다른 방법도 있다.
  • 각각의 그룹의 시작 인덱스들을 배열 A에 저장하고, 각 그룹의 사이즈로 이루어진 수열 B를 최댓값 세그먼트 트리에 저장한다.
  • 쿼리 (l,r) 이 들어오면, A배열에서 바이너리 서치를 해서, l과 r이 몇번째 그룹에 속하는지를 찾는다.
  • A[x]<l<A[x+1] 이고 A[y]<r<A[y+1] 이라고 하면, 최대 빈도수는 (A[x+1]-l), (r-A[y]), max(B[x+1:y]) 중에서 최댓값이 된다. max(B[x+1:y])은 세그먼트 트리로 구해주면 된다.
  • 여기에서는 A와 B배열의 크기가 그룹의 갯수, 즉 사용된 페인트의 종류이다. 이것을 P라고 하자. 그러면 바이너리 서치도 O(logP), 세그먼트 트리에서 쿼리도 O(logP)가 되므로, 쿼리 한개를 O(logP)에 처리 가능하다. 전처리는 A와 B를 만드는데에 O(n), 세그먼트 트리를 만드는데에 O(P) 이므로 총 O(n+P+logP)가 된다. P⇐n 이므로 윗 방법보다 효율적이고, P랑 n이 비슷하더라도 상수값이 적어서 더 실제로 더 빨리 돌아간다. 최적화에 신경을 거의 안쓴것도 있긴 하지만.. 윗 방법으로는 3400ms정도에, 이 방법으로는 688ms에 통과되었다.

"""Solution code for "BOJ 12986. 화려한 마을2".

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

import sys
import typing
from teflib import segmenttree


class Node(typing.NamedTuple):
    l_val: int
    r_val: int
    l_count: int = 1
    r_count: int = 1
    max_count: int = 1


def merge(l, r):
    l_count = l.l_count
    r_count = r.r_count
    max_count = max(l.max_count, r.max_count)
    if l.r_val == r.l_val:
        if l.l_val == l.r_val:
            l_count += r.l_count
        if r.l_val == r.r_val:
            r_count += l.r_count
        max_count = max(max_count, l.r_count + r.l_count)
    return Node(l.l_val, r.r_val, l_count, r_count, max_count)


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    brightness = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree(
        (Node(l_val=x, r_val=x) for x in brightness),
        merge=merge)
    for _ in range(Q):
        X, Y = [int(x) for x in sys.stdin.readline().split()]
        print(segtree.query(X - 1, Y).max_count)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree

"""Solution code for "BOJ 12986. 화려한 마을2".

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

import bisect
import itertools
import sys
from teflib import segmenttree


def main():
    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)


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree