c언어 14427번 수열과 쿼리 15 (백준)

#include <stdio.h>

typedef struct Node{ //구조체 : 최솟값, 인덱스
   int min, index;
}Node;

Node a[100001]; //요소들을 담는 배열
Node tree[400004]; //트리들을 담는 배열

Node min(Node x, Node y) { //최솟값 찾기
    if(x.min != y.min) return (x.min < y.min) ? x : y; //값이 다르다면 더 작은 값의 구조체를 반환
    else return (x.index < y.index) ? x : y; //값이 같다면, 더 인덱스가 작은 값의 구조체를 반환
}

Node init(int start, int end, int node) { //트리 초기화
    if(start == end) return tree[node]= a[start];
    int mid = (start+end)/2;
    return tree[node] = min(init(start, mid, node*2), init(mid+1, end, node*2+1));
}

void update(int start, int end, int node, int index) { //트리값 갱신
    if(index < start || index > end) return;
    if(start == end) {
    	if(start == index) tree[node] = a[index];
    	return; 
	}
    
    int mid = (start+end)/2;
    update(start, mid, node*2, index);
    update(mid+1, end, node*2+1, index);
    tree[node] = min(tree[node*2], tree[node*2+1]);
}


int main(void) {
    int n, m;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
    	scanf("%d", &a[i].min);
    	a[i].index = i; 
	}
    init(1, n, 1); //트리를 초기화 합니다.
    
    scanf("%d", &m);
    while(m--) {
        int b, c, d;
        scanf("%d", &b);
        if(b==1) {
        	scanf("%d %d", &c, &d);
        	a[c].min = d; //요소를 갱신하고
            update(1, n, 1, c); //요소와 관련된 트리들의 최솟값을 바꿔줍니다.
        }
        else {
            printf("%d\n", tree[1].index); //모든 요소의 최솟 값은 tree의 root에 있습니다.
        }
    }
    
}

 

풀이 : segment tree

1. 배열들을 구조체로 만듭니다.

2. n을 입력 받습니다

3. n개의 요소들을 입력 받습니다.

4. 트리 배열을 초기화 합니다.

5. m을 입력 받습니다.

6. 1을 입력 받으면 값을 갱신합니다, 관련된 트리의 값도 갱신합니다.

7. 모든 요소들의 최솟값을 출력합니다 (이는 tree의 root값에 있는 최솟값을 의미합니다)

 

https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15