Informatica Online Judge

  Range Minimum Query [1401 / 0579]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 55   Total Tried : 83


The Champion of this Problem (C++) : admin - ms / 800byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

RMQ란 정보과학에서 다양한 분야에 활용되는 문제이다.

주어진 구간에 대해서 최솟값을 구하는 쿼리들에 대해서 답을 구하면 된다.

그리고 갱신도 가능하도록 구현하면 다양하게 활용할 수 있다.

예를 들어 주어진 집합이

5 2 1 4 6

이라고 하면

1~5까지의 최솟값을 구하면 모든 원소의 최솟값이 1을 구하면 되며

4~5까지의 최솟값을 구하면 4와 6중 더 작은 4를 구하면 된다.

임의의 집합이 주어지고 구간의 최솟값을 구하거나, 특정 값을 갱신하는 쿼리를 처리하는 프로그램을 작성하시오.

Input

첫 번째 줄에 자료의 수를 나타내는 정수 n과 쿼리의 수 q가 공백으로 구분되어 입력도니다.

둘째 줄에는 n개의 자료가 공백으로 구분되어 입력된다.

셋째 줄부터 q줄에 걸쳐서 쿼리가 입력된다.

쿼리는 쿼리의 종류를 나타내는 자연수 1, 2 중 하나로 시작된다.

쿼리 종류 1은 구간의 최솟값을 구하는 쿼리로 구간의 시작과 끝을 나타내는 자연수 l, r이 주어진다.

즉 1 l r의 형태로 주어진다.

쿼리의 종류 2는 두 자연수 a, b가 공백으로 구분되어 입력된다. 각 값의 의미는 a번째 값을 b로 바꾸라는 쿼리이다.

즉 2 a b의 형태로 주어진다.

[입력값의 정의역]
2 <= n <= 100,000
1 <= q <= 100,000
1 <= l <= r <= n
1 <= a <= 100,000
0 <= b, 배열의 값 <= 32,767

쿼리는 항상 1번 쿼리가 2번 쿼리보다 많음이 보장된다.

Output

각 1번 쿼리에 대해서 최솟값을 한 줄에 하나씩 출력한다.

IO Example

입력
5 3
5 2 1 4 6
1 1 5
2 2 0
1 1 5

출력
1
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]