[BOJ] 백준 14438번 : 수열과 쿼리 17 (JAVA)

문제

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

 

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 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번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

 

 

풀이

세그먼트 트리를 이용하여 풀 수 있는 문제였습니다.

 

전반적인 컨셉은 '10868번 최솟값' 문제와 유사했습니다. 이 문제에 대해 아직 풀어보지 않으신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 10868번 : 최솟값 (JAVA)

 

 

위 로직을 사용하여 init과 query 메소드를 구현하고, 특정 값을 다른 값으로 바꾸는 update 메소드를 구현해 주시면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.