그냥 세그먼트 트리로 최소트리, 최대트리 구현하면 끝나는 문제이다.
#include<stdio.h>
#include<algorithm>
using namespace std;
long long arr[100004];
long long max_seg[300004],min_seg[300004];
int N,M;
void max_init(int n, int s, int e)
{
if(s==e)
{
max_seg[n] = arr[s];
return;
}
int m = (s+e)/2;
max_init(n*2,s,m);
max_init(n*2+1,m+1,e);
max_seg[n] = max(max_seg[n*2],max_seg[n*2+1]);
return;
}
long long min_init(int n, int s, int e)
{
if(s==e)
{
return min_seg[n] = arr[s];
}
int m = (s+e)/2;
return min_seg[n] = min(min_init(n*2,s,m),min_init(n*2+1,m+1,e));
}
long long max_find(int n, int s, int e, int fs, int fe)
{
if(fs>e || s>fe) return 0;
if(fs<=s && e<=fe)
{
return max_seg[n];
}
int m = (s+e)/2;
return max(max_find(n*2,s,m,fs,fe),max_find(n*2+1,m+1,e,fs,fe));
}
long long min_find(int n, int s, int e, int fs, int fe)
{
if(fs>e || s>fe) return 1000000004;
if(fs<=s && e<=fe)
{
return min_seg[n];
}
int m = (s+e)/2;
return min(min_find(n*2,s,m,fs,fe),min_find(n*2+1,m+1,e,fs,fe));
}
int main()
{
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++)
{
scanf("%lld",&arr[i]);
}
max_init(1,1,N);
min_init(1,1,N);
for(int i=1;i<=M;i++)
{
int a,b;
scanf("%d %d",&a,&b);
long long x = min_find(1,1,N,a,b);
long long y = max_find(1,1,N,a,b);
printf("%lld %lld\n",x,y);
}
}구현 연습 문제였다.
init을 int를 반환하는 거랑 void 2가지로 짜면서 연습해봤다.
