SegmentTree[구간의 최대값 구하기]

반응형

정수로 이뤄진 수열을 입력 받은 다음, 수열의 임의의 연속된 구간의 최대값을 구하는 프로그램을 작성한다.

수열의 원소는 번호가 매겨지는데, 맨 앞의 원소부터 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; } Colored by Color Scripter

cs