문제 주소 : www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
문제 확인
전 문제 최솟값 문제와 풀이 방식이 같은 문제입니다.
[백준] 10868번 : 최솟값
문제 주소 : www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와..
latter2005.tistory.com
풀이
최대/최소에 따라 세그먼트 트리의 구조는 변함이 없으므로 하나의 구조체에 최댓값, 최솟값 모두 기록 해 둡니다. 그 후 탐색 시 한 번에 연산하여 찾아냅니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <cstdio>
#include <algorithm>
#include <sys/stat.h>
#include <sys/mman.h>
class fio {
size_t rsize;
unsigned char* rbuf;
static const int wsize = 0x7eeee;
unsigned char wbuf[wsize];
int ridx, widx;
public:
fio() : ridx(0), widx(0) {
struct stat rstat;
fstat(0, &rstat);
rsize = rstat.st_size;
rbuf = (unsigned char*)mmap(0, rsize, PROT_READ, MAP_FILE | MAP_PRIVATE, 0, 0);
}
inline bool isBlank() {
return
!(rbuf[ridx] != '\n' && rbuf[ridx] != '\t' && rbuf[ridx] != '\r' &&
rbuf[ridx] != '\f' && rbuf[ridx] != '\v' && rbuf[ridx] != ' ');
}
inline void consumeBlank() { while (isBlank()) ridx++; }
int readInt() {
int res = 0, flag = 0;
consumeBlank();
if (rbuf[ridx] == '-') {
flag = 1;
ridx++;
}
while (!isBlank() && ridx < rsize)
res = 10 * res + rbuf[ridx++] - '0';
return flag ? -res : res;
}
inline void flush() {
fwrite(wbuf, 1, widx, stdout);
widx = 0;
}
inline int intSize(int x) {
int cnt = 1;
x = (x > 0) ? x : -x;
while (x /= 10) cnt++;
return cnt;
}
inline void check(int n) { if (widx + n >= wsize) flush(); }
inline void writeChar(char z) { check(1); wbuf[widx++] = z; }
void writeInt(int x) {
int sz = intSize(x);
check(sz);
if (x < 0) {
writeChar('-');
x = -x;
}
for (int i = 1; i <= sz; ++i) {
wbuf[widx + sz - i] = x % 10 + '0';
x /= 10;
}
widx += sz;
}
};
using namespace std;
typedef struct node {
int min, max;
}node;
int main() {
fio fo;
node min_max_tree[200002];
int n = fo.readInt(), m = fo.readInt();
for (int i = 0; i < n; i++)
min_max_tree[n + i].max = min_max_tree[n + i].min = fo.readInt();
for (int i = n - 1; i > 0; i--) {
min_max_tree[i].min = min(min_max_tree[i << 1].min, min_max_tree[i << 1 | 1].min);
min_max_tree[i].max = max(min_max_tree[i << 1].max, min_max_tree[i << 1 | 1].max);
}
while (m--) {
int s = fo.readInt(), e = fo.readInt(), min_val = 0x7fffffff, max_val = 0x80000000;
for (s += n - 1, e += n; s < e; s >>= 1, e >>= 1) {
if (s & 1) {
min_val = min(min_max_tree[s].min, min_val);
max_val = max(min_max_tree[s++].max, max_val);
}
if (e & 1) {
min_val = min(min_max_tree[--e].min, min_val);
max_val = max(min_max_tree[e].max, max_val);
}
}
fo.writeInt(min_val);
fo.writeChar(' ');
fo.writeInt(max_val);
fo.writeChar('\n');
}
fo.flush();
}
|
cs |
반응형
'알고리즘 문제 > [백준]' 카테고리의 다른 글
| [백준] 8895 막대 배치 (0) | 2020.12.18 |
|---|---|
| [백준] 15685 드래곤 커브 (0) | 2020.12.17 |
| [백준] 10868 최솟값 (0) | 2020.12.15 |
| [백준] 1744 수 묶기 (0) | 2020.12.12 |
| [백준] 19236 청소년 상어 (0) | 2020.12.09 |