[C++]백준 - 2357번 문제

2357번: 최솟값과 최댓값 (acmicpc.net)

2357번: 최솟값과 최댓값

 

2357번 : 최솟값과 최댓값

---

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

 

입력

---

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

 

 

출력

---

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

 

 

---

 

생각해 볼 점

---

세그먼트 트리 문제입니다.

 

11505번 문제와 동일한 방식으로 구현하면 되지만,

 

세그먼트 트리를 작성할 때

 

1. 최소값을 저장하는 세그먼트 트리

2. 최대값을 저장하는 세그먼트 트리

 

두 가지를 작성할 필요가 있습니다.

 

저 같은 경우에는 pair<min, max>와 같은 방식으로 하나의 pair 트리를 만들었습니다.

 

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

//s ~ e 범위에서 left ~ right 범위를 쿼리
pair<int, int> query(pair<int, int> seg[], int s, int e, int node, int left, int right)
{
    if(right < s || e < left) return {1000000000, 1};
    if(left <= s && e <= right) return seg[node];
    
    int mid = (s + e) / 2;
    
    pair<int, int> A, B;
    A = query(seg, s, mid, node * 2 + 1, left, right);
    B = query(seg, mid + 1, e, node * 2 + 2, left, right);
    
    return {min(A.first, B.first), max(A.second, B.second)};
}

//세그먼트 트리 만들기
pair<int, int> make_seg(int arr[], pair<int, int> seg[], int s, int e, int node)
{
    if(s == e) return seg[node] = {arr[s], arr[s]};
    int mid = (s + e) / 2;
    
    pair<int, int> A, B;
    A = make_seg(arr, seg, s, mid, node * 2 + 1);
    B = make_seg(arr, seg, mid + 1, e, node * 2 + 2);
    return seg[node] = {min(A.first, B.first), max(A.second, B.second)};
}


int main() 
{
    int N, M;
	scanf("%d %d", &N, &M);
	
	int *arr = new int[N];
	pair<int, int> *seg = new pair<int, int>[N << 2];       //<최솟값, 최댓값>
	for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
	
	make_seg(arr, seg, 0, N - 1, 0);
	
	for(int i = 0; i < M; i++) 
	{
	    int a, b;
	    scanf("%d %d", &a, &b);
	    a--; b--;
	    pair<int, int> queried = query(seg, 0, N - 1, 0, a, b);
	    printf("%d %d\n", queried.first, queried.second);
	}
	return 0;
}

 

그 외

---