14438번: 수열과 쿼리 17
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을
www.acmicpc.net
1 i v -> i번째 수를 v로 바꿉니다.
2 i j -> i ~ j 번째 수들 중에서 가장 작은 값을 출력합니다.
배열의 원소를 입력받을 때마다 세그먼트 트리로 최솟값을 갱신시켜줍니다.
그리고 쿼리를 입력받습니다.
1이면 i번째 수를 v로 바꾸는 update,
2이면 i ~ j번째 수들 중 가장 작은 값을 출력하는 query를 실행시킵니다.
현재 구간[s, e]이 찾으려는 구간[l, r]의 밖에 있으면 INF를 리턴,
완전히 포함되어있으면 tree[node]를 리턴합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <algorithm>
#define INF 2147483647
using namespace std;
int tree[400004];
int N, M;
int update(int node, int s, int e, int idx, int diff) {
if (idx < s || idx > e) return tree[node];
if (s == e) return tree[node] = diff;
int m = (s + e) / 2;
return tree[node] = min(update(node * 2, s, m, idx, diff), update(node * 2 + 1, m + 1, e, idx, diff));
}
int query(int node, int s, int e, int l, int r) {
if (l <= s && e <= r) return tree[node];
if (l > e || r < s) return INF;
int m = (s + e) / 2;
return min(query(node * 2, s, m, l, r), query(node * 2 + 1, m + 1, e, l, r));
}
void func() {
int type, a, b;
cin >> M;
while (M--) {
cin >> type >> a >> b;
if (type == 1) {
update(1, 1, N, a, b);
}
else {
cout << query(1, 1, N, a, b) << '\n';
}
}
}
void input() {
int x;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> x;
update(1, 1, N, i, x);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 14719 빗물 (0) | 2021.03.15 |
|---|---|
| boj 2304 창고 다각형 (0) | 2021.02.25 |
| boj 13537 수열과 쿼리 1 (0) | 2021.02.21 |
| boj 6549 히스토그램에서 가장 큰 직사각형 (0) | 2021.02.19 |
| boj 2104 부분배열 고르기 (0) | 2021.02.19 |