[백준/14438] 수열과 쿼리 17 (Python)

Problem : https://www.acmicpc.net/problem/14438

14438번: 수열과 쿼리 17

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:07:08

 

---

 

문제 설명

 

 

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

 

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 10^9)
• 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 출력한다. (1 ≤ i ≤ j ≤ N)

 

수열의 인덱스는 1부터 시작한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

넷째 줄부터 M개의 줄에는 쿼리가 주어진다.

 

출력

 

2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

 

입력 예시

 

5
5 4 3 2 1
6
2 1 3
2 1 4
1 5 3
2 3 5
1 4 3
2 3 5

 

출력 예시

 

3
2
2
3

 

 

---

 

풀이

 

요즘 쿼리 문제만 풀다보니 세그먼트 트리는 바로바로 튀어나오는 지경이다. O(logN)의 시간복잡도로 구간 최솟값과 업데이트가 가능한 세그먼트 트리를 사용하는 골자의 문제이다.

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = float('inf')

N = int(input())
nums = list(map(int, input().split()))
tree = [MAX]*(4*N)

def init(start, end, idx) :
  if start == end :
    tree[idx] = nums[start]
    return
  mid = (start + end) // 2
  init(start, mid, idx*2)
  init(mid+1, end, idx*2+1)
  tree[idx] = min(tree[idx*2], tree[idx*2+1])

def update(start, end, idx, target, val) :
  if start > target or end < target :
    return
  if start == end :
    tree[idx] = val
    return
  mid = (start + end) // 2
  update(start, mid, idx*2, target, val)
  update(mid+1, end, idx*2+1, target, val)
  tree[idx] = min(tree[idx*2], tree[idx*2+1])

def search(start, end, idx, left, right) :
  if right < start or end < left :
    return MAX
  if left <= start <= end <= right :
    return tree[idx]
  mid = (start + end) // 2
  lval = search(start, mid, idx*2, left, right)
  rval = search(mid+1, end, idx*2+1, left, right)
  return min(lval, rval)

init(0, N-1, 1)
M = int(input())
for _ in range(M) :
  q, i, j = map(int, input().split())
  if q == 1  :
    update(0, N-1, 1, i-1, j)
  else :
    print(search(0, N-1, 1, i-1, j-1))

풀이 완료!