[문제풀이] 14706번: 구간 합 최대
문제유형
세그먼트 트리
Solution
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 57 58 59 60 61 62 | #include <stdio.h> #define MAXN 50000 #define MAXT (50000*2*2) int N, Q; //원소의 갯수, 구간의 갯수 int tree[MAXT]; #define MAX(a,b) ((a > b) ? (a) : (b)) void update_new_data(int node, int s, int e, int idx, int d) { int m; if (s == e) { tree[node] = d; return; } m = (s + e) / 2; if (idx <= m) update_new_data(node * 2, s, m, idx, d); else update_new_data(node * 2 + 1, m + 1, e, idx, d); tree[node] = MAX(tree[node * 2], tree[node * 2 + 1]); } int query(int node, int s, int e, int qs, int qe) { int m; int left, right; if (qs <= s && e <= qe) { return tree[node]; } else if (s > qe || e < qs) return 0; m = (s + e) / 2; left = query(node * 2, s, m, qs, qe); right = query(node * 2 + 1, m + 1, e, qs, qe); return MAX(left, right); } int main() { int i, j; scanf("%d %d", &N, &Q); for (i = 1; i <= N; i++) //데이터 입력반기. { int input = 0; scanf("%d", &input); update_new_data(1, 1, N, i, input); } for (i = 0; i < Q; i++) //구간의 최댓값 구하기. { int start = 0, end = 0; scanf("%d %d", &start, &end); printf("%d\n", query(1, 1, N, start, end)); } return 0; } | cs |
'한국으로 > 알고리즘 문제풀이' 카테고리의 다른 글
[문제풀이] 1406번: 에디터 (0) | 2018.07.05 |
---|---|
[문제풀이] 2776번: 암기왕 (0) | 2018.07.04 |
[문제풀이] 1966번: 프린터 큐 (0) | 2018.07.04 |
[문제풀이] 5926번: Cow Lineup (0) | 2018.07.04 |
[문제풀이] 1395번: 스위치 (0) | 2018.07.04 |
[문제풀이] 7432번: 디스크 트리 (0) | 2018.07.04 |
[문제풀이] 5052번: 전화번호 목록 (0) | 2018.07.04 |
[문제풀이] 6593번: 상범 빌딩 (0) | 2018.07.04 |