Algorithm/BOJ

최솟값과 최댓값 - 2357

jhg0406 2020. 3. 13. 20:16
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
//2357 - 최솟값과 최댓값
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1000000001
 
int N, M;
int arr[100001];
 
struct SegmentTree
{
    int n;
    vector<int> mintree;
    vector<int> maxtree;
 
    SegmentTree(int n) : n(n), mintree(n*4+1), maxtree(n*4+1)
    {
        mininit(1, n, 1);
        maxinit(1, n, 1);
    }
 
    int mininit(int left, int right, int node)
    {
        if(left == right) return mintree[node] = arr[left];
        int mid = (left + right)/2;
        return mintree[node] = min(mininit(left, mid, node*2), mininit(mid+1, right, node*2+1));
    }
 
    int maxinit(int left, int right, int node)
    {
        if(left == right) return maxtree[node] = arr[left];
        int mid = (left + right)/2;
        return maxtree[node] = max(maxinit(left, mid, node*2), maxinit(mid+1, right, node*2+1));
    }
 
    int queryMin(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if(nodeRight < left || right < nodeLeft) return INF;
        if(left <= nodeLeft && nodeRight <= right)
            return mintree[node];
        
        int mid = (nodeLeft + nodeRight) / 2;
        return min(queryMin(left, right, nodeLeft, mid, node*2), 
                   queryMin(left, right, mid+1, nodeRight, node*2+1));
    }
 
    int queryMax(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if(nodeRight < left || right < nodeLeft) return 0;
        if(left <= nodeLeft && nodeRight <= right)
            return maxtree[node];
        
        int mid = (nodeLeft + nodeRight) / 2;
        return max(queryMax(left, right, nodeLeft, mid, node*2), 
                   queryMax(left, right, mid+1, nodeRight, node*2+1));
    }
 
    int queryMin(int left, int right)
    {   
        return queryMin(left, right, 1, n, 1);
    }
 
    int queryMax(int left, int right)
    {
        return queryMax(left, right, 1, n, 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i];
    SegmentTree st(N);
    int x, y;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y;
        cout << st.queryMin(x,y) << " " << st.queryMax(x, y) << "\n";
    }
}
 cs

 

 

 

 

 

 

 

https://www.acmicpc.net/problem/2357

 

2357번: 최솟값과 최댓값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을

www.acmicpc.net

 

 

 

 

 

 

 

최솟값과 최댓값

세그먼트 트리를 이용해 구간의 최소값과 최대값을 빠르게 구할수 있습니다.