2357

각 구간별로 최소값과 최대값을 구하는 문제

가장 쉽게 생각하면 매번 구간이 주어질 때마다 최대값과 최소값을 구하는 방법이 있겠으나

그렇게 쉽게 문제를 냈을 리가 없다.

방법은 Min Max Tree를 만드는 것이다

옛날 자료구조 시간에 Tree의 존재를 배우기는 했으나 직접 구현하지는 않아봐서

이번에 구현하는데 시간이 좀 걸렸고,,,

구간 부분을 지정해주는 것도 꽤 힘들었다.

(이거 진짜 귀찮은 작업이다...)

하지만 한번에 맞춰서 기분이 좋다

나의 미천한 코딩실력도 조금씩 상승하는 것 같은 느낌이다.

#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<fstream> using namespace std; int minTree[20][100000]; int maxTree[20][100000]; int mypow(int b){ int ret = 1; for(int i = 0; i < b; i++) ret*=2; return ret; } int main(){ int size, testcase; int tmp; ifstream ifp("input.txt"); ifp>>size>>testcase; //scanf("%d %d", &size, &testcase); for(int i=0; i<size; i++){ ifp>>tmp; //scanf("%d", &tmp); minTree[0][i]=maxTree[0][i]=tmp; } int bef=0; int next=1; while(1){ //make min max Tree for(int i=0; i<size; i+=2){ if(minTree[bef][i+1]!=0) minTree[next][i/2]=min(minTree[bef][i], minTree[bef][i+1]); else minTree[next][i/2]=minTree[bef][i]; maxTree[next][i/2]=max(maxTree[bef][i], maxTree[bef][i+1]); } bef++; next++; if(size==2) break; if(size%2==1) size++; size/=2; } int from, to; int piv; int root = bef; for(int i=0; i<testcase; i++){ ifp>>from>>to; //scanf("%d %d", &from, &to); from--; to--; vector<int> minChecker, maxChecker; queue<pair<int, int> > q; q.push(make_pair(root, 0)); while(!q.empty()){ pair<int, int> fro = q.front(); q.pop(); int node_from = fro.second*mypow(fro.first); int node_to = (fro.second+1)*mypow(fro.first)-1; if(node_from >= from && node_to <= to) { minChecker.push_back(minTree[fro.first][fro.second]); maxChecker.push_back(maxTree[fro.first][fro.second]); } else{ if(node_from > to) { } else if(node_to < from) { } else{ //내려가본다 q.push(make_pair(fro.first-1, fro.second*2)); q.push(make_pair(fro.first-1, fro.second*2+1)); } } } int res_min = 1000000001, res_max=0; for(int i = 0; i < minChecker.size(); i++){ res_min = min(minChecker[i], res_min); res_max = max(maxChecker[i], res_max); } printf("%d %d\n", res_min, res_max); } return 0; }