BOJ2357 최솟값과 최댓값
문제
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이하의 값을 갖는다.
해설
단순히 특정 구간의 최솟값과 최댓값을 각각 배열에 저장한다면 메모리초과를 피할 수 없다.
따라서, 세그먼트 트리를 활용하여 최솟값,최댓값 트리를 만들어 준다.
접근방식 1 (dfs)
#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;
long long n,m,arr[100001],maxTree[400004],minTree[400004];
long long maxInit(int s,int e,int x){
if(s==e)return maxTree[x]=arr[s];
int mid=(s+e)/2;
return maxTree[x]=max(maxInit(s,mid,x*2),maxInit(mid+1,e,x*2+1));
}long long minInit(int s,int e,int x){
if(s==e)return minTree[x]=arr[s];
int mid=(s+e)/2;
return minTree[x]=min(minInit(s,mid,x*2),minInit(mid+1,e,x*2+1));
}long long maxQuery(int s,int e,int l,int r,int x){
if(l>e||r<s)return 0;
if(l<=s&&e<=r)return maxTree[x];
int mid=(s+e)/2;
return max(maxQuery(s,mid,l,r,x*2),maxQuery(mid+1,e,l,r,x*2+1));
}long long minQuery(int s,int e,int l,int r,int x){
if(l>e||r<s)return INF;
if(l<=s&&e<=r)return minTree[x];
int mid=(s+e)/2;
return min(minQuery(s,mid,l,r,x*2),minQuery(mid+1,e,l,r,x*2+1));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++){
cin >> arr[i];
}maxInit(0,n-1,1);
minInit(0,n-1,1);
while(m--){
int a,b;
cin >> a >> b;a--;b--;
cout << minQuery(0,n-1,a,b,1) << ' ' << maxQuery(0,n-1,a,b,1) << '\n';
}
}