白駿10868号:最高値
質問する
題ショートカットキー>白駿10868号:最高値
に答える
Indexed Treeを用いて区間最大値問題を解く.以前の解の白駿2357号:最高価格と最低価格で最大値を探す以外は,同じ解である.これでO(logn)で区間最高値を見つけることができます!詳しい説明は注釈を参考にして分かりやすいと思います!
#include<iostream>
#include<vector>
#define INF 1000000001
using namespace std;
vector<int> IDT; // indexed tree (구간 최솟값을 저장)
int N, M, num, a, b, tsize=1;
void init(){ // 앞서 초기화한 leaf node 값을 가지고 internal node들을 구간 최솟값으로 채워 나감
for(int i=tsize-1; i>0; i--)
IDT[i] = min(IDT[i<<1], IDT[(i<<1)|1]);
}
int minQuery(int l, int r){
l+=(tsize-1); r+=(tsize-1); // tree에 알맞는 index로 변환
int min_value = INF;
while (l<=r){
if((l&1)==1) min_value = min(min_value, IDT[l]); // tree의 right일 때 값을 취함
if((r&1)==0) min_value = min(min_value, IDT[r]); // tree의 left일 때 값을 취함
l = (l+1)>>1; // (left+1)/2 node로 이동
r = (r-1)>>1; // (right-1)/2 node로 이동
}
return min_value;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
while(tsize<N) tsize<<=1; // tree size를 구하기 위해 N보다 크면서 N과 가장 가까운 2의 거듭제곱을 구함
IDT.resize(tsize<<1); // tree size 설정
for(int i=1; i<IDT.size(); i++) IDT[i] = INF; // minQuery시 비교를 위해 초기화
for(int i=tsize; i<tsize+N; i++){ // tree의 leaf node들을 입력 값으로 채움
cin >> num;
IDT[i] = num;
}
init(); // IDT를 만듦
for(int i=0; i<M; i++){
cin >> a >> b;
cout << minQuery(a, b) << '\n'; // [a, b]구간 최솟값 출력
}
}
Reference
この問題について(白駿10868号:最高値), 我々は、より多くの情報をここで見つけました https://velog.io/@danbibibi/백준-10868번-최솟값テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol