[최솟값과 최댓값-백준] / 세그먼트 트리 응용

Problem

---

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

2357번: 최솟값과 최댓값

Solve

---

세그먼트 트리 - 이진트리 구조 / 각 노드는 특정 구간에 대한 합, 최솟값, 최댓값 등을 가질 수 있다.

 

ios:sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

이거 추가해야 시간초과 안뜹니다.

 

이것 때문인줄 모르고 이런저런 방식들로 구현함

 

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

using namespace std;

struct mem
{
	int min;
	int max;
};

class sol
{
	vector<int> arr;
	int* max_arr;
	int* min_arr;

	//mem* max_min;
	//mem* min;

	int arr_size;

	int max_val;
	int min_val;
    
    // 풀이 1 =========================================================
    void init(int start, int end, int node)
	{
		if (start == end)
		{
			max_arr[node] = min_arr[node] = arr[start];
			return;
		}
		int mid = (start + end) / 2;
		init(start, mid, node * 2);
		init(mid + 1, end, node * 2 + 1);
		min_arr[node] = min(min_arr[node * 2], min_arr[node * 2 + 1]);
		max_arr[node] = max(max_arr[node * 2], max_arr[node * 2 + 1]);
		return;
	}

	void find_(int start, int end, int left, int right, int node)
	{
		if (left > end || right < start)
		{
			return;
		}
		if (left <= start && end <= right)
		{
			min_val = min_val < min_arr[node] ? min_val : min_arr[node];
			max_val = max_val > max_arr[node] ? max_val : max_arr[node];
			return;
		}
		int mid = (start + end) / 2;
		find_(start, mid, left, right, node * 2);
		find_(mid + 1, end, left, right, node * 2 + 1);
		return;
	}
    // =================================================================


	// 풀이 2 =========================================================
	/*mem node_init(int start, int end, int node)
	{
		if (start == end)
		{
			mem row{ arr[start], arr[start] };
			return max_min[node] = row;
		}

		int mid = (start + end) / 2;
		mem a = node_init(start, mid, node * 2);
		mem b = node_init(mid + 1, end, node * 2 + 1);
		int n_min, n_max;
		n_min = a.min < b.min ? a.min : b.min;
		n_max = a.max > b.max ? a.max : b.max;
		mem row{ n_min,n_max };
		return max_min[node] = row;
	}

	mem find_node(int start, int end, int left, int right, int node)
	{
		if (left > end || right < start)
		{
			mem row{ 1000000000,0 };
			return row;
		}

		if (start >= left && end <= right)
		{
			min_val = min_val < max_min[node].min ? min_val : max_min[node].min;
			max_val = max_val > max_min[node].max ? max_val : max_min[node].max;
			mem row{ min_val,max_val };
			return row;
		}
		int mid = (start + end) / 2;
		mem a = find_node(start, mid, left, right, node * 2);
		mem b = find_node(mid + 1, end, left, right, node * 2 + 1);
		min_val = a.min < b.min ? a.min : b.min;
		max_val = a.max > b.max ? a.max : b.max;
		mem row{ min_val,max_val };
		return row;
	}*/
    
    // =================================================================

	
	// 풀이 3 =========================================================
	/*int max_init(int start, int end, int node)
	{
		if (start == end)
		{
			return max_arr[node] = arr[start];
		}

		int mid = (start + end) / 2;
		int a = max_init(start, mid, node * 2);
		int b = max_init(mid + 1, end, node * 2 + 1);
		return max_arr[node] = a > b ? a : b;
	}

	int find_max(int start, int end, int left, int right, int node)
	{
		if (right < start || left > end)
		{
			return 0;
		}

		if (start >= left && end <= right)
		{
			return max_val = max_val > max_arr[node] ? max_val : max_arr[node];
		}

		int mid = (start + end) / 2;

		int a = find_max(start, mid, left, right, node * 2);
		int b = find_max(mid + 1, end, left, right, node * 2 + 1);
		return max_val = a > b ? a : b;
	}

	int min_init(int start, int end, int node)
	{
		if (start == end)
		{
			return min_arr[node] = arr[start];
		}

		int mid = (start + end) / 2;
		int a = min_init(start, mid, node * 2);
		int b = min_init(mid + 1, end, node * 2 + 1);
		return min_arr[node] = a > b ? b : a;
	}

	int find_min(int start, int end, int left, int right, int node)
	{
		if (start > right || end < left)
		{
			return 1000000000;
		}

		if (left <= start && right >= end)
		{
			return min_val = min_val < min_arr[node] ? min_val : min_arr[node];
		}
		int mid = (start + end) / 2;
		int a = find_min(start, mid, left, right, node * 2);
		int b = find_min(mid + 1, end, left, right, node * 2 + 1);
		return min_val = a > b ? b : a;
	}*/
    
    // =================================================================

public:
	sol(const int& N)
	{
		arr_size = N;
		arr.reserve(N);

		//max_min = new mem[N * 4];
		max_arr = new int[N * 4];
		min_arr = new int[N * 4];
		for (int i = 0; i < N; i++)
		{
			int num;
			cin >> num;
			arr.push_back(num);
		}


		max_val = 0;
		min_val = 1000000000;
		init(0, N - 1, 1);
		/*max_init(0, N - 1, 1);
		min_init(0, N - 1, 1);*/
		//node_init(0, N - 1, 1);
	}

	void answer()
	{
		int a, b;
		cin >> a >> b;
		find_(0, arr_size - 1, a - 1, b - 1, 1);
		/*find_max(0, arr_size - 1, a - 1, b - 1, 1);
		find_min(0, arr_size - 1, a - 1, b - 1, 1);*/
		//find_node(0, arr_size - 1, a - 1, b - 1, 1);
		cout << min_val << " " << max_val << '\n';
		max_val = 0;
		min_val = 1000000000;
	}

};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	sol S(N);

	for (int i = 0; i < M; i++)
	{
		S.answer();
	}
	return 0;
}