전형적인 세그먼트 트리 문제이다. 일단 시간 제한이 2초이기 때문에 일일이 10만개의 정수 쌍 입력에 대해 10만개의 배열에서 최솟값과 최댓값을 뒤지게 되면 복잡도가 터지게 된다.
이를 위해 미리 답들을 트리 형태로 저장해놓는 세그먼트 트리를 사용하여 복잡도를 줄일 수 있다.
값을 저장할 때마다 최솟값과 최댓값을 log(n) 의 복잡도로 저장해놓는 식이다. 그 후 정수 쌍 입력을 받을 때마다 만들어 두었던 세그먼트 트리에 query를 날리는 식으로 문제를 풀게 되면 답이 금방 나오게 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
LL max_tree[1 << 20];
LL min_tree[1 << 20];
LL min_query_seg(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 1000000000;
if (l <= s && e <= r) return min_tree[node];
else
return min(min_query_seg(node * 2, s, (s + e) / 2, l, r),
min_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
LL max_query_seg(int node, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return max_tree[node];
else
return max(max_query_seg(node * 2, s, (s + e) / 2, l, r),
max_query_seg(node * 2 + 1, (s + e) / 2 + 1, e, l, r));
}
void update_seg(int node, int s, int e, int idx, int v) {
if (idx < s || e < idx) return;
if (s == e) {
max_tree[node] = v;
min_tree[node] = v;
}
else {
update_seg(node * 2, s, (s + e) / 2, idx, v);
update_seg(node * 2 + 1, (s + e) / 2 + 1, e, idx, v);
max_tree[node] = max(max_tree[node * 2], max_tree[node * 2 + 1]);
min_tree[node] = min(min_tree[node * 2], min_tree[node * 2 + 1]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
LL n, m;
LL a, b;
scanf("%lld %lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a);
update_seg(1, 1, n, i, a);
}
pair<LL, LL> ans;
for (int i = 0; i < m; i++) {
scanf("%lld %lld", &a, &b);
printf("%lld ", min_query_seg(1, 1, n, a, b));
printf("%lld\n", max_query_seg(1, 1, n, a, b));
}
return 0;
}
