[BOJ] 10868. 最高値

最高値
アルゴリズム区分:セグメントツリー、データ構造、疎配列
質問する
n(1≦N≦100000)個の整数の場合,aからbまでの整数の中から最小の整数を探すことは困難ではない.しかし,このようなa,b対がM(1≦M≦100000)個あると,難題となる.この問題を解決してみる.
ここで、aは入力順aの物語である.たとえば、a=1、b=3の場合、入力された順序で1、2、3個の整数の中で最適な値を検索する必要があります.各整数の値は1以上10000000以下です.
入力
1行目はN,Mです.次のN行にはN個の整数がある.次のM行にはa,b対があります.
しゅつりょく
各a,bの答えは、M行に入力された順に出力される.
入力例1
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
サンプル出力1
5
38
20
5
問題を解く
段木を学ぶために、わざわざ関連するタイプの問題を探して解答し、段木を実施して問題を解いた.
そうでなければ、この問題を見ていると、この問題ではM回繰り返し、入力区間ごとの最大値を出力して時間制限が1秒であることを理解する必要があるので、時間の複雑さを重視します.従って、セグメントツリーを実装することによって、時間的複雑さを低減する必要があるという問題を特定しなければならない.
セグメントツリーはツリー構造であり,時間的複雑度はO(logn)である.したがって,入力を受信するたびに全区間を巡回ナビゲーションするO(N)時間の複雑さと比較して,TLEなしで交流を受信することができる.
セグメントツリー実装は,最も一般的なセグメントツリー実装を行えば解決できる問題である.したがって,これはセグメントツリーを学習する立場から学ぶことができる問題であると考えられる.
まずセグメントツリーを直接表し、以下に示す.

ソースコードではinit関数は最初に入力した値(N行)のセグメントツリーを構成する関数であり,その後のM回入力区間で最適値を求める関数はfindmin関数である.
Init関数:セグメントツリーを実装する必要がある円アレイの開始idxと終了idx、およびセグメントツリーの開始点をパラメータとしてセグメントツリーを実装する
findMin関数:検索する区間をleftとrightパラメータとして受け入れ、その配列の全区間からstartとendとして開始し、セグメントツリーから検索する点をノード変数として、範囲を縮小し、その区間の最大値の関数を検索します.
ソースコード

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define maxNum 100,000

int n, m;
vector<int> num;
vector<int> tree;
int init(int start, int end, int node);
int findMin(int start, int end, int node, int left, int right);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    tree.resize(4 * n);
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        num.push_back(input);
    }

    init(0, n -1, 1);

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << findMin(0, n - 1, 1, a - 1, b - 1) << endl;
    }

    return 0;
}

// start : 시작 idx, end : 마지막 idx
int init(int start, int end, int node) {
    if(start == end) {
        return tree[node] = num[start];
    }
    int mid = (start + end) / 2;
    
    // 둘 중의 더 최솟값이 해당 노드의 값이 됨
    return tree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}

// start : 시작 idx, end : 끝 idx, left, right : 최솟값을 구하는 범위
int findMin(int start, int end, int node, int left, int right) {
    // 범위 밖에 있는 경우
    if(left > end || right < start) return 1000000001;
    
    // 범위 안에 있는 경우
    if(left <= start && end <= right) return tree[node];
    
    // 범위를 더 쪼개야 하는 경우
    int mid = (start + end) / 2;
    return min(findMin(start, mid, node * 2, left, right), findMin(mid + 1, end, node * 2 + 1, left, right));
}

題出所:https://www.acmicpc.net/problem/108682

カイドウ草が白駿で「そうだ!!」判定を受けた