반응형
정수로 이뤄진 수열을 입력 받은 다음, 수열의 임의의 연속된 구간의 최대값을 구하는 프로그램을 작성한다.
수열의 원소는 번호가 매겨지는데, 맨 앞의 원소부터 1, 2, ... 순으로 숫자가 매겨진다.
[입출력 예시]
입력 : 4 3 1 3 2 4 1 2 2 4 1 1
출력 : 3 4 1
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
|
#include <stdio.h>
#define maxx(a,b) ((a)>(b)?(a):(b))
#define NUM_DATA (50002) //5만
#define MAX_TREE (NUM_DATA*3)
//#define MOD 1000000007
typedef long long ll;
int tree[MAX_TREE];
int arr[NUM_DATA + 1]; // 0번 index 공간 무시
int N, Q;
void Update_New_Data(int node, int s, int e, int idx, int data){
int m;
if (s == e){
tree[node] = data;
return;
}
m = (s + e) / 2;
if (idx <= m) Update_New_Data(node * 2, s, m, idx, data);
else Update_New_Data(node * 2 + 1, m + 1, e, idx, data);
tree[node] = maxx(tree[node * 2], tree[node * 2 + 1]);
}
//구간 정보 요청 함수
int Query(int node, int s, int e, int qs, int qe){
int m;
int l, r, ret;
if (qs <= s && e <= qe) return tree[node];
else if (qs > e || s > qe) return 1;
m = (s + e) / 2;
l = Query(node * 2, s, m, qs, qe);
r = Query(node * 2 + 1, m + 1, e, qs, qe);
ret = maxx(l, r);
return ret;
}
int main(void){
int from, to;
scanf("%d %d", &N, &Q);
for (int i = 1; i <= N; i++)
scanf("%d", &arr[i]);
for (int i = 1; i <= N; i++)
Update_New_Data(1, 1, N, i, arr[i]); // 세그먼트 트리 생성
for (int i = 0; i < Q; i++) {
scanf("%d %d", &from, &to);
printf("%d\n", Query(1, 1, N, from, to));
}
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이' 카테고리의 다른 글
[Hash]Open Address 방식 (0) | 2020.10.07 |
---|---|
[Heap]Heap Sort (0) | 2020.10.07 |
[Heap]MaxHeap구성 (0) | 2020.10.07 |
[HEAP] minheap 구성 (0) | 2020.10.07 |
[BOJ.16985번] Maaaaaaaaaze (2) | 2019.03.15 |