https://www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
세그먼트 트리 알고리즘 기본 문제 중 하나입니다.
import java.util.*;
import java.io.*;
public class Main {
public static long mintree[];
public static long maxtree[];
public static long minselect(int start,int end,int node,long left,long right){
if(end<left||start>right){
return Long.MAX_VALUE;
}
if(right>= end && left <= start){//5>=4 && 1<=0
return mintree[node];
}
int mid=(start+end)/2;
return Math.min( minselect(start,mid,node*2,left,right), minselect(mid+1,end,node*2+1,left,right));
}
public static long MinbuildingTree(int start,int end, int node, long arr[]){
if(start==end){
return mintree[node]=arr[start];
}
int mid=(start+end)/2;
return mintree[node]=Math.min(MinbuildingTree(start,mid,node*2,arr), MinbuildingTree(mid+1,end,node*2+1,arr) );
}
public static long MaxbuildingTree(int start,int end, int node, long arr[]){
if(start==end){
return maxtree[node]=arr[start];
}
int mid=(start+end)/2;
return maxtree[node]=Math.max(MaxbuildingTree(start,mid,node*2,arr), MaxbuildingTree(mid+1,end,node*2+1,arr) );
}
public static long maxselect(int start,int end,int node,long left,long right){
if(end<left||start>right){
return 0;
}
if(right>= end && left <= start){//5>=4 && 1<=0
return maxtree[node];
}
int mid=(start+end)/2;
return Math.max( maxselect(start,mid,node*2,left,right), maxselect(mid+1,end,node*2+1,left,right));
}
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
long arr[]=new long[n];
mintree=new long[n*4];
maxtree=new long[n*4];
for(int i=0;i<n;i++){
long tmp=scan.nextLong();
arr[i]= tmp;
}
MinbuildingTree(0,n-1,1,arr);
MaxbuildingTree(0,n-1,1,arr);
for(int i=0;i<m;i++){
long left=scan.nextLong()-1;
long right=scan.nextLong()-1;
long mins=minselect(0,n-1,1,left,right);
long maxs=maxselect(0,n-1,1,left,right);
System.out.println(mins+" "+maxs);
}
}
}