사용자 도구

사이트 도구


ps:problems:boj:14428

수열과 쿼리 16

ps
링크https://www.acmicpc.net/problem/14428
출처BOJ
문제 번호14428
문제명수열과 쿼리 16
레벨골드 1
분류

구간 쿼리

시간복잡도O(n+mlogn)
인풋사이즈n<=100,000, m<=100,000
사용한 언어Python
제출기록49720KB / 1352ms
최고기록1352ms
해결날짜2021/03/20

풀이

  • 수열과 쿼리 15에서 최솟값 쿼리 범위가 항상 전체로 되어 있던 것을, 구간 쿼리로 바꾼 문제이다.
  • 수열과 쿼리 15에서 세그먼트 트리를 쓰는 방법 외에도, 우선순위큐를 써서 풀 수 있었지만, 이제는 세그먼트 트리를 써야만 한다. 세그먼트 트리로 푸는 방법은 똑같다. 그냥 각 노드에 값 대신에, (값, 인덱스)의 튜플을 저장해주면 구간 최솟값을 위한 세그먼트 트리를 그대로 사용해서 풀수 있다.
  • 시간 복잡도는 세그먼트 트리 구축에 O(n)이 필요하고 m개의 쿼리를 각각 O(logn)에 처리하므로 O(n+mlogn)이다.

코드

"""Solution code for "BOJ 14428. 수열과 쿼리 16".

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

import sys
from teflib import segmenttree


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    segtree = segmenttree.SegmentTree((a_i, i + 1) for i, a_i in enumerate(A))
    M = int(sys.stdin.readline())
    for i in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, v = query
            segtree.set(i - 1, (v, i))
        else:
            _, i, j = query
            print(segtree.query(i - 1, j)[1])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U X E E A
 
ps/problems/boj/14428.txt · 마지막으로 수정됨: 2021/04/30 15:16 저자 teferi