鉄則本 A10 - Resort Hotel (2Q, ★4)

左右からの累積和・累積 max を前処理で求めておくのは、よくある典型！！

• 問題へのリンク

問題概要

個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。

【クエリ】
区間 が与えられるので、数列からその区間を除外した領域について、整数値の最大値を求めよ。

制約

• 

考えたこと

左右から累積 max を求める。つまり、次の値を求める！

• left[i] ← 数列のうち、左から 個分についての最大値
• right[i] ← 数列のうち、右から 個分についての最大値

これを求めておくと、数列から区間 を除外して残るのは

• 左から 個分
• 右から 個分

なので、求める答えは max(left[L-1], right[N-R]) となる。計算量は となる。

github.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 左右からの累積 max を求める
    int N, D;
    cin >> N;
    vector<int> A(N), left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) {
        left[i + 1] = max(left[i], A[i]);
        right[i + 1] = max(right[i], A[N - i - 1]);
    }
    
    // クエリ
    cin >> D;
    for (int d = 0; d < D; ++d) {
        int L, R;
        cin >> L >> R;
        
        // 左から L-1 個の部屋、右から N-R 個の部屋は使える
        int res = max(left[L - 1], right[N - R]);
        cout << res << endl;
    }
}