수열과 쿼리 15

• 업데이트 쿼리와 구간 최솟값 쿼리를 살짝 변형해서, 구간 최솟값의 인덱스를 물어보는 문제이다.
• 그냥 각 노드에 값 대신에, (값, 인덱스)의 튜플을 저장해주면 구간 최솟값을 위한 세그먼트 트리를 그대로 사용해서 풀수 있다.
• 하지만, 이 문제는 부분구간이 아니라 전체 범위에서의 최솟값만을 묻는데, 그렇다면 세그먼트 트리가 아니라 우선순위큐로도 해결이 가능하다.
  • 사실, 세그먼트 트리보다 우선순위큐가 먼저 떠올라야 하는게 정상인거 같은데, '수열과 쿼리' 시리즈가 다 구간 쿼리만 다루다 보니까 오히려 잘 안떠올랐다. 문제에 태그도 세그먼트 트리만 걸려있다.
• teflib.priorityqueue.UpdatableHeap 을 써서 업데이트를 처리해도 되지만, 그냥 그 로직을 코드에 직접 구현한 이유는 그렇게 해도 심플하게 처리되어서이다.
• 시간 복잡도는 어느쪽으로 하든 O(n+mlogn)이지만, 우선순위큐 버전이 세그먼트 트리버전보다 3배가량 빨랐다.

• 51624KB / 468ms

"""Solution code for "BOJ 14427. 수열과 쿼리 15".

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

import sys
import heapq


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    heap = [(a_i, i + 1) for i, a_i in enumerate(A)]
    heapq.heapify(heap)
    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
            heapq.heappush(heap, (v, i))
            A[i - 1] = v
            while heap[0][0] != A[heap[0][1] - 1]:
                heapq.heappop(heap)
        else:
            print(heap[0][1])


if __name__ == '__main__':
    main()

• 50312KB / 1384ms

"""Solution code for "BOJ 14427. 수열과 쿼리 15".

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

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:
            print(segtree.query(0, N)[1])


if __name__ == '__main__':
    main()

• Dependency: teflib.segmenttree.SegmentTree