[C++] 2357번 최솟값과 최댓값 - 자료 구조, 세그먼트 트리

#include <iostream>
#include <algorithm>
#include <vector>

#define FOR(i, k, N) for(int i=k; i<=N; i++)
#define MAX_N 100001
#define INF 1000000001
#define X first
#define Y second

using namespace std;

int N, M;  //정수의 개수 N, 질문의 개수 M
int num[MAX_N];  //수열
vector<pair<int, int>> tr;  //세그먼트 트리(최댓값, 최솟값)

void input()
{
    cin >> N >> M;
    FOR(i, 1, N) cin >> num[i];
    tr.resize(MAX_N*4);
}

pair<int, int> init(int s, int e, int no)  //세그먼트 트리
{
    if(s==e) {
        tr[no].X = tr[no].Y = num[s];
        return tr[no];
    }
    int m = (s+e)/2;
    pair<int, int> lres = init(s, m, no*2);
    pair<int, int> rres = init(m+1, e, no*2+1);
    
    return tr[no] = {max(lres.X, rres.X), min(lres.Y, rres.Y)};  //최댓값과 최솟값을 반환
}

pair<int, int> sum(int s, int e, int no, int l, int r)
{
    if(l>e || r<s) return {-INF, INF};
    if(l<=s && e<=r) return tr[no];
    
    int m=(s+e)/2;
    pair<int, int> lres = sum(s, m, no*2, l, r);
    pair<int, int> rres = sum(m+1, e, no*2+1, l, r);
    
    return {max(lres.X, rres.X), min(lres.Y, rres.Y)};  //반환된 최댓값들과 최솟값들 중에서 선택해 반환
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    init(1, N, 1);
    
    FOR(i, 1, M) {
        int a, b; cin >> a >> b;
        pair<int, int> res = sum(1, N, 1, a, b);
        cout << res.Y << ' ' << res.X << '\n';
    }
    
    return 0;
}

2042번 구간 합 구하기

https://leyamon.tistory.com/entry/C-2042%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC

[C++] 2042번 구간 합 구하기 - 자료 구조, 세그먼트 트리

와 똑같은 문제. 합을 구하는 것을 최댓값과 최솟값 연산으로 바꾸면 된다.

 

이 문제는 굳이 세그먼트 트리를 업데이트할 필요가 없기 때문에(즉, 최댓값과, 최솟값이 하나로 결정되면 끝이기 때문에) 

 

트리를 굳이 구축해줄 필요 없이 그냥 배열에다가 DP형태?로 풀면 바로 끝난다. 다른 사람 코드를 보다가 그런 코드가 있어서 아래에 링크를 적어두었다.

 

 

 

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/15841742

로그인

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.