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))
