BOJ 10868 최솟값

LONGNEW·2021년 9월 12일
0

BOJ

목록 보기
270/333

https://www.acmicpc.net/problem/10868
시간 1초, 메모리 256MB

input :

  • N M (1 ≤ N, M ≤ 100,000)
  • N개의 정수
  • M개의 줄에는 a, b의 쌍

output :

  • M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력

조건 :

  • a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것

구간에서의 최솟값을 찾는 것이 O(N)에 대한 시간복잡도를 가진다면 당연히 시간 초과가 발생할 것이다.
O(lgN)의 시간복잡도라면 어지간하면 1초의 시간에는 충족한다.

그러면 가장 최근에 공부하던 펜윅 트리를 사용해서 최솟값을 찾으려 하는데 이 때 우리는 2개의 트리를 이용해야 한다.

update

일단 배열을 입력을 받으면서 tree 값을 계속 업데이트 해야 한다.
그러고 난 후에 마지막에 구간을 입력 받아 이에 대한 정답을 출력하는 방식을 사용한다.

tree_start

이 트리의 경우 1 ~ 구간 까지의 최솟값을 각 위치에 저장하도록 한다.
그래서 idx도 2의 보수를 더하는 방식을 사용한다.

tree_end

이 트리의 경우 구간 ~ end 까지의 최솟값을 각 위치에 저장하도록 한다.
그래서 idx도 2의 보수를 빼는 방식을 사용한다.

query

query라는 이름 자체가 좀 무섭긴 한데 별 거 없다. 그저 질문(조건)을 주는 것이고 이에 대한 리턴을 얻는 것 뿐이다.

input : start, end
start ~ end 까지의 최솟값을 물어서 리턴으로 그 값을 가지고 간다.

그 때 가장 주의 해야 할 것.
현재의 idx 값이 의도치 않게 구간 외의 값이 저장된 노드값을 비교하면 안 된다.
그래서 cur_parent가 반복문의 조건이 되게 한다.

cur ~ cur_parent 까지의 최솟값이 저장된 구간을 확인 해도 될까요??? 하는 의미라고 생각하면 된다.

그리고 이 cur가 2의 보수를 더하는 방식에서는 tree_end에서 값을 가져오고
빼는 방식은 tree_start에서 값을 가져온다. 이에 대한 이유는 논문의 그림을 보면 이해하기 쉬운데 end의 위치의 경우 각 idx가 의도치 않은 구간을 완벽히 제하고 필요한 구간만 가져온다.

암튼 그렇게 하고보면 가장 큰 2의 완전 제곱수가 문제이다.
왜냐하면 얘는 어쩔 수 없이
[1 ~ 2의 완전 제곱 수], [2의 완전 제곱 수 ~ end] 까지의 값을 모두 비교한 값을 가지고 있어서 의도치 않은 연산이 생길 수 있다.

그냥 더함

원래의 배열 data[가장 큰 놈]을 비교해서 그냥 리턴하면 된다.

import sys


def update(idx, val):
    update_start(idx, val)
    update_end(idx, val)


def update_start(idx, val):
    while idx <= n:
        tree_start[idx] = min(tree_start[idx], val)
        idx += (idx & -idx)


def update_end(idx, val):
    while idx > 0:
        tree_end[idx] = min(tree_end[idx], val)
        idx -= (idx & -idx)


def query(start, end):
    ret = float('inf')

    cur = start
    cur_parent = cur + (cur & -cur)
    while cur_parent <= end:
        ret = min(ret, tree_end[cur])
        cur = cur_parent
        cur_parent += (cur_parent & -cur_parent)

    cur = end
    cur_parent = cur - (cur & -cur)
    while cur_parent >= start:
        ret = min(ret, tree_start[cur])
        cur = cur_parent
        cur_parent -= (cur_parent & -cur_parent)

    ret = min(ret, data[cur])
    return ret


n, m = map(int, sys.stdin.readline().split())
tree_start, tree_end = [float('inf')] * (n + 1), [float('inf')] * (n + 1)
data = [0] * (n + 1)

for i in range(1, n + 1):
    data[i] = int(sys.stdin.readline())
    update_start(i, data[i])
    update_end(i, data[i])

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())

    print(query(a, b))

0개의 댓글