[백준/C++] 2357번: 최솟값과 최댓값
1653 단어 Indexed TreeIndexed Tree
방법
indexed tree 알고리즘
1. IDT_min[MAX] & IDT_max[MAX] 초기화
2. lgMin( ) & lgMax( ) 함수 구현
코드
#include<bits/stdc++.h>
#define MAX 100001
#define INF 1000000001
using namespace std;
typedef long long ll;
int N, M, B;
ll IDT_min[MAX * 4];
ll IDT_max[MAX * 4];
void initIDT() {
for (int i = B - 1; i > 0; i--) { // 부모트리 생성하기
IDT_min[i] = min(IDT_min[i * 2], IDT_min[(i * 2) + 1]);
}
for (int i = B - 1; i > 0; i--) {
IDT_max[i] = max(IDT_max[i * 2], IDT_max[(i * 2) + 1]);
}
}
ll lgMin(int l, int r) { // l ~ r 중 최솟값
l += (B - 1);
r += (B - 1);
ll Min = INF;
while (l <= r) {
if ((l % 2) == 1) Min = min(Min, IDT_min[l]);
if ((r % 2) == 0) Min = min(Min, IDT_min[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return Min;
}
ll lgMax(int l, int r) { // l ~ r 중 최댓값
l += (B - 1);
r += (B - 1);
ll Max = 0;
while (l <= r) {
if ((l % 2) == 1) Max = max(Max, IDT_max[l]);
if ((r % 2) == 0) Max = max(Max, IDT_max[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return Max;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M;
for (B = 1; B < N; B *= 2); // 첫번째 왼쪽 index 구하기
for (int i = B, n; i < N + B; i++) {
cin >> IDT_min[i];
IDT_max[i] = IDT_min[i];
}
initIDT();
for (int i = 0, a, b; i < M; i++) {
cin >> a >> b; // a ~ b번째 사이 최솟값, 최댓값
cout << lgMin(a, b) << " " << lgMax(a, b) << "\n";
}
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 2357번: 최솟값과 최댓값), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@0inn/백준C-2357번-최솟값과-최댓값저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)