BOJ 2357 | 최솟값과 최댓값

수업 때 핸드폰으로 풀다가 어딘가 상당히 어긋난 채로 오류투성이 코드를 만들었던 문제...

세그먼트 트리를 사용하는 것이 현명해 보이지만 최근 구간 쿼리에 입문하려고 하고 있기 때문에 평방 분할을 사용하여 문제를 풀어보았다.

반례도 올라온 게 거의 없어서 중간에 애를 많이 먹었는데 혹시나 평방 분할로 푸는 사람들을 위해 조금 첨부해보겠다.

20
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
18 19

Ans
18 19

20
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1

Ans
1 1

20
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 20

Ans
20 20

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'



int N, M;
vector<int> v;
vector<pair<int, int>> dividesum;

void divide(){
	int k = sqrt(N);
	int s = 0;
	vector<int> part;
	for (int i = 0; i < N; i++){
		if ( i % k == 0 && i != 0){
			dividesum.push_back(make_pair( *min_element(part.begin(), part.end()) , *max_element(part.begin(), part.end()) ));
			part.clear();
			s = 0;
		}
		part.push_back(v[i]);
	}
	dividesum.push_back(make_pair( *min_element(part.begin(), part.end()) , *max_element(part.begin(), part.end()) ));
}

pair<int,int> query(int a, int b){
	vector<int> checkmax;
	vector<int> checkmin;
	int k = sqrt(N);
	for (int i = 0; i < dividesum.size(); i++){
		if ( (i+1)*k > a ) {
			
			int ik = min((i+1)*k, b+1);
			
			for (int j = a; j < ik; j++){
				checkmax.push_back(v[j]);
				checkmin.push_back(v[j]);
			}
			
			//debug << "First Check\n";
			//for (auto i : checkmin) debug << i << endl;
			
			for (int j = i+1; (j+1)*k <= b+1; j++){
				checkmin.push_back(dividesum[j].first);
				checkmax.push_back(dividesum[j].second);
			}
			
			//debug << "Second Check\n";
			//debug << "i is " << i << endl;
			//for (auto i : checkmin) debug << i << endl;
			
			int bk = min(b-a, (b+1)%k);
			for (int j = 0; j < bk; j++){
				checkmin.push_back(v[b]);
				checkmax.push_back(v[b--]);
			}
			
			//debug << "Last Check\n";
			//for (auto i : checkmin) debug << i << endl;
			//debug << "</>Last Check\n";
			
			break;
		}
	}
	return make_pair(*min_element(checkmin.begin(), checkmin.end()), *max_element(checkmax.begin(), checkmax.end()));
}

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		v.push_back(t);
	}
	
	if (N != 1)
		divide();

	for (int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		
		if (N == 1){
			cout << v[0] << ' ' << v[0] << endl;
			continue;
		}
		
		pair<int, int> tmp = query(a-1, b-1);
		cout << tmp.first << ' ' << tmp.second << '\n';
	}
	return 0;
}