概要

連続区間 \([l,r]\) が「山型」であり、かつ区間内の最大標高と最小標高の差が \(K\) 以上であるもののうち、長さの最大値を求める問題です。

区間を右端から順に伸ばしながら、「現在の右端 \(r\) で終わる最長の山型区間」を管理します。

考察

山型の条件を、隣り合う峰の標高差の符号で考えます。

• \(H_i < H_{i+1}\) なら「上り」
• \(H_i > H_{i+1}\) なら「下り」
• \(H_i = H_{i+1}\) なら山型にはできない

山型とは、

\[ 上り, 上り, \ldots, 上り, 下り, 下り, \ldots, 下り \]

のように、途中で高くなり続け、その後は低くなり続ける形です。

つまり、山型でない原因は主に次の 2 つです。

1. 隣接する標高が等しい場所を含む
2. 一度「下り」になった後に、再び「上り」が現れる

例えば、

\[ 1, 3, 5, 4, 2 \]

は山型ですが、

\[ 1, 3, 2, 4 \]

は「上り \(\to\) 下り \(\to\) 上り」となっているため山型ではありません。

---

素朴にすべての区間 \([l,r]\) を調べると、区間数は \(O(N^2)\) 個あります。
さらに各区間について山型判定や最大値・最小値を求めると、\(N \leq 10^6\) では到底間に合いません。

そこで、右端 \(r\) を左から右へ動かしながら、

• 現在の \(r\) で終わる最長の山型区間の左端 \(L\)
• その区間内の最大値・最小値

を効率よく管理します。

---

重要な点は、固定した右端 \(r\) に対して、最長の山型区間 \([L,r]\) を考えれば十分であることです。

もし \([L,r]\) の最大値と最小値の差が \(K\) 以上なら、それが右端 \(r\) の候補の中で最長です。

逆に、\([L,r]\) の差が \(K\) 未満なら、その中に含まれるより短い区間では、最大値と最小値の差はそれ以上大きくなりません。
したがって、右端 \(r\) の区間には候補が存在しません。

アルゴリズム

左端 \(L\) を、「現在の右端 \(r\) に対して、\([L,r]\) が山型になる最小の位置」として管理します。

また、直近の「下り」がどこで起きたかを lastDown として持ちます。

山型区間の左端 \(L\) の更新

右端を \(r\) に進めたとき、直前の峰 \(H_{r-1}\) と比較します。

1. \(H_{r-1} = H_r\) の場合

等しい標高を含む区間は山型になりません。

したがって、区間は \(r\) から始めるしかありません。

\[ L = r \]

とします。

2. \(H_{r-1} > H_r\) の場合

これは「下り」です。

山型では、下りは許されます。
ただし、後で「上り」が来たときに問題になるため、この下りの位置を記録します。

\[ lastDown = r - 1 \]

とします。

3. \(H_{r-1} < H_r\) の場合

これは「上り」です。

もし以前に「下り」があった場合、

\[ 下り \to 上り \]

という形になり、山型ではなくなります。

そのため、最後に起きた下りを区間から除外する必要があります。
最後の下りが \(lastDown\)、つまり

\[ H_{lastDown} > H_{lastDown+1} \]

だったなら、この下りを含まないように

\[ L \geq lastDown + 1 \]

とします。

よって、

\[ L = \max(L, lastDown + 1) \]

と更新します。

---

最大値・最小値の管理

各 \(r\) について区間 \([L,r]\) の

\[ \max(H_L,\ldots,H_r) \]

と

\[ \min(H_L,\ldots,H_r) \]

を高速に求める必要があります。

これには単調キューを使います。

• maxdq: 区間内の最大値候補を管理する deque
• mindq: 区間内の最小値候補を管理する deque

maxdq では、標高が大きい順になるようにインデックスを保持します。
先頭が常に現在の区間の最大値です。

mindq では、標高が小さい順になるようにインデックスを保持します。
先頭が常に現在の区間の最小値です。

右端 \(r\) を追加するとき、

• maxdq では、後ろから \(H_r\) 以下の要素を取り除く
• mindq では、後ろから \(H_r\) 以上の要素を取り除く

ことで、単調性を保ちます。

また、左端 \(L\) より左にあるインデックスは区間外なので、deque の先頭から削除します。

---

各 \(r\) について、

\[ diff = \max(H_L,\ldots,H_r) - \min(H_L,\ldots,H_r) \]

を求め、

\[ diff \geq K \]

なら、答えを

\[ r - L + 1 \]

で更新します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

各インデックスは deque に高々 1 回追加され、高々 1 回削除されるため、全体で線形時間です。

実装のポイント

lastDown は「最後に下りが発生した位置」を表します。

コードでは 0-indexed で管理しているため、

if (H[r - 1] > H[r]) {
    lastDown = r - 1;
}

となっています。

また、等しい標高が現れた場合は、その隣接ペアを含む区間はすべて山型ではないので、

L = r;

として区間をリセットします。

最大値・最小値を管理する deque では、左端 \(L\) が進んだ後に、区間外のインデックスを必ず削除します。

while (!maxdq.empty() && maxdq.front() < L) maxdq.pop_front();
while (!mindq.empty() && mindq.front() < L) mindq.pop_front();

これにより、常に deque の先頭が現在の区間 \([L,r]\) に含まれる最大値・最小値になります。

ソースコード

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

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

    int N;
    long long K;
    cin >> N >> K;

    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    int L = 0;
    int lastDown = -1;
    int ans = 0;

    deque<int> maxdq, mindq;

    for (int r = 0; r < N; r++) {
        if (r > 0) {
            if (H[r - 1] == H[r]) {
                L = r;
            } else if (H[r - 1] > H[r]) {
                lastDown = r - 1;
            } else {
                L = max(L, lastDown + 1);
            }
        }

        while (!maxdq.empty() && H[maxdq.back()] <= H[r]) maxdq.pop_back();
        maxdq.push_back(r);

        while (!mindq.empty() && H[mindq.back()] >= H[r]) mindq.pop_back();
        mindq.push_back(r);

        while (!maxdq.empty() && maxdq.front() < L) maxdq.pop_front();
        while (!mindq.empty() && mindq.front() < L) mindq.pop_front();

        if (!maxdq.empty() && !mindq.empty()) {
            long long diff = H[maxdq.front()] - H[mindq.front()];
            if (diff >= K) {
                ans = max(ans, r - L + 1);
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。