[BOJ] 2357 - 최솟값과 최댓값

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

BOJ - 최솟값과 최댓값

문제 유형: 세그먼트 트리

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 192MB

 

문제

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에 대한 답을 최솟값, 최댓값 순서로 출력한다.

 

풀이

두 개의 세그먼트 트리를 만들 것이다.

하나는 구간의 최소 값만을 가지는 세그먼트 트리, 또 하나는 구간의 최대 값만을 가지는 세그먼트 트리이다.

두 세그먼트 트리를 동시에 빌드하고, 동시에 쿼리를 조사할 수 있다.

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>
#define LIMIT 100001

using namespace std;

int n, m;
int arr[LIMIT], minSeg[4 * LIMIT], maxSeg[4 * LIMIT];

void build(int index, int l, int r) {
  if (l == r) {
    minSeg[index] = arr[l];
    maxSeg[index] = arr[l];
    return;
  }

  int mid = (l + r) / 2;
  build(index * 2, l, mid);
  build(index * 2 + 1, mid + 1, r);
  minSeg[index] = min(minSeg[index * 2], minSeg[index * 2 + 1]);
  maxSeg[index] = max(maxSeg[index * 2], maxSeg[index * 2 + 1]);
}

pii query(int index, int ql, int qr, int l, int r) {
  if (ql > r || qr < l) {
    return {INT_MAX, INT_MIN};
  }

  if (ql <= l && r <= qr) {
    return {minSeg[index], maxSeg[index]};
  }

  int mid = (l + r) / 2;
  auto lq = query(index * 2, ql, qr, l, mid);
  auto rq = query(index * 2 + 1, ql, qr, mid + 1, r);

  return {min(lq.first, rq.first), max(lq.second, rq.second)};
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
  }

  build(1, 1, n);

  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    pii res = query(1, a, b, 1, n);

    cout << res.first << " " << res.second << "\n";
  }

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var (
	arr    []int32
	minSeg []int32
	maxSeg []int32
)

func min(a, b int32) int32 {
	if a > b {
		return b
	}
	return a
}

func max(a, b int32) int32 {
	if a < b {
		return b
	}
	return a
}

func build(index, l, r int32) {
	if l == r {
		minSeg[index] = arr[l]
		maxSeg[index] = arr[r]
		return
	}

	mid := (l + r) / 2
	build(index*2, l, mid)
	build(index*2+1, mid+1, r)
	minSeg[index] = min(minSeg[index*2], minSeg[index*2+1])
	maxSeg[index] = max(maxSeg[index*2], maxSeg[index*2+1])
}

func query(index, ql, qr, l, r int32) (int32, int32) {
	if ql > r || qr < l {
		return math.MaxInt32, math.MinInt32
	}

	if ql <= l && r <= qr {
		return minSeg[index], maxSeg[index]
	}

	mid := (l + r) / 2
	lmin, lmax := query(index*2, ql, qr, l, mid)
	rmin, rmax := query(index*2+1, ql, qr, mid+1, r)

	return min(lmin, rmin), max(rmax, lmax)
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m int32
	fmt.Fscan(reader, &n, &m)
	arr = make([]int32, n+1)
	minSeg = make([]int32, 4*(n+1))
	maxSeg = make([]int32, 4*(n+1))

	for i := int32(1); i <= n; i++ {
		fmt.Fscan(reader, &arr[i])
	}

	build(1, 1, n)

	for i := int32(0); i < m; i++ {
		var a, b int32
		fmt.Fscan(reader, &a, &b)
		minima, maxima := query(1, a, b, 1, n)

		fmt.Fprintln(writer, minima, maxima)
	}
}