[BOJ] 2357 최솟값과 최댓값

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

 

 

소스 코드:

#include <iostream>
#include <string.h>
#include <queue>
#include <functional>
#include <algorithm>
#define SIZE 100001*4
#define MAX 1000000000
using namespace std;

int n,m,large[SIZE], small[SIZE];

int large_update(int pos,int val,int x,int y,int node)
{
	if (pos > y || pos < x) return large[node];
	if (x == y) return large[node]=val;
	int mid = (x + y) >> 1;
	return large[node] = max(large_update(pos, val, x, mid, node * 2), large_update(pos, val, mid + 1, y, node * 2 + 1));
}
int small_update(int pos, int val, int x, int y, int node) {
	if (pos > y || pos < x) return small[node];
	if (x == y) return small[node] = val;
	int mid = (x + y) >> 1;
	return small[node] = min(small_update(pos, val, x, mid, node * 2), small_update(pos, val, mid + 1, y, node * 2 + 1));
}
int small_query(int hi,int low,int x,int y,int node)
{
	if (y<low || x>hi) return MAX;
	if (low <= x&&hi >= y) return small[node];
	int mid = (x + y) >> 1;
	return min(small_query(hi, low, x, mid, node * 2), small_query(hi, low, mid + 1, y, node * 2 + 1));
}
int large_query(int hi, int low, int x, int y, int node)
{
	if (y<low || x>hi) return 0;
	if (low <= x&&hi >= y) return large[node];
	int mid = (x + y) >> 1;
	return max(large_query(hi, low, x, mid, node * 2), large_query(hi, low, mid + 1, y, node * 2 + 1));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m;

	fill(small, small + n * 4 + 1, MAX);
	int temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;

		small_update(i, temp, 0, n - 1, 1);
		large_update(i, temp, 0, n - 1, 1);
	}
	int q, w;
	for (int i = 0; i < m; i++)
	{
		cin >> q >> w;
		cout<<small_query(w-1,q-1, 0, n - 1, 1)<<' '
			<<large_query(w-1,q-1, 0, n - 1, 1)<<'\n';
	}
	return 0;
}