[BOJ] 2357. 最高価格と最低価格

3559 ワード
セグメントツリー データ構造 テキストリンク
最高価格と最低価格
アルゴリズム区分:セグメントツリー、データ構造
質問する
n(1≦N≦100000)個の整数の場合、1番目の整数から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対があります.
しゅつりょく
M行に入力された順に、a,b毎の答えが最も切り上げられ、最低価格の順に出力される.
入力例1
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
サンプル出力1
5 100
38 100
20 81
5 81
問題を解く
セグメントツリーの問題を解決し続けています.
この問題は昨日解いた10868.最高価格の問題を解くの論理と同じだ.違いは、最高価格がまだ存在することだ.最初はpair資料型を利用しようと思っていたのですが、まず最高値で、その後は最安値で記憶する方式で実現して、実力がまだ足りないためかTLEを手に入れました.TLEが得られる理由については、さらに考慮する必要があるかもしれない.TLEが出現したので,それぞれ最高値のセグメントツリーと最低値のセグメントツリーを実現して交流を受信する.実装プロセスは、上記のハイパーリンクの問題と同じです.アレイ全体を巡回するのに要する時間の複雑さが非常に大きいため、巡回中に見つけるためにO(logn)に減らすことができるセグメントツリーを作成することができる.
ソースコード
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define MAX 100000

int n, m;
vector<int> v(100001, 0);
int maxTree[4 * MAX];
int minTree[4 * MAX];
int minInit(int start, int end, int node);
int maxInit(int start, int end, int node);
int findMin(int start, int end, int node, int left, int right);
int findMax(int start, int end, int node, int left, int right);

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

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }

    minInit(0, n - 1, 1);
    maxInit(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) << " " << findMax(0, n - 1, 1, a - 1, b- 1) << endl;
    }

    return 0;
}

int minInit(int start, int end, int node) {
    if(start == end) {
        return minTree[node] = v[start];
    }

    int mid = (start + end) / 2;
    return minTree[node] = min(minInit(start, mid, node * 2), minInit(mid + 1, end, node * 2 + 1));
}

int maxInit(int start, int end, int node) {
    if(start == end) {
        return maxTree[node] = v[start];
    }

    int mid = (start + end) / 2;
    return maxTree[node] = max(maxInit(start, mid, node * 2), maxInit(mid + 1, end, node * 2 + 1));
}

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 minTree[node];
    
    int mid = (start + end) / 2;
    return min(findMin(start, mid, node * 2, left, right), findMin(mid + 1, end, node * 2 + 1, left, right));
}

int findMax(int start, int end, int node, int left, int right) {
    if(left > end || right < start) return 0;

    if(left <= start && end <= right) return maxTree[node];
    
    int mid = (start + end) / 2;
    return max(findMax(start, mid, node * 2, left, right), findMax(mid + 1, end, node * 2 + 1, left, right));
}
  • 題出所:https://www.acmicpc.net/problem/23572
  • カイドウ草が白駿で「そうだ!!」判定を受けた
    • 学習Python -中級コース:17日、Tkinter -高速かつ簡単にGUIアプリケーションを作成する方法です.
    React_7. Effect Hook