概要

この問題は、配列の要素の変更（点更新）を行いながら、指定された区間における隣接要素の差の「最大値」および「2番目に大きい値」を高速に求める問題です。

値の更新と区間クエリを効率的に処理するために、セグメント木（Segment Tree）を使用します。

---

考察

1. 問題の言い換え

チェックポイント \(i\) と \(i+1\) の標高差の絶対値を \(d_i = |A_i - A_{i+1}|\) とします。 登山者が区間 \([l, r]\) を歩くとき、考慮すべき標高差の集合は \(S = \{d_l, d_{l+1}, \ldots, d_{r-1}\}\) です。

このとき、青木君が経験する疲労度は以下のように整理できます。 - \(l = r\) のとき: 隣接ペアがないため、疲労度は \(0\)。 - 最大値 \(M_1 \le K\) のとき: 回避を行わないため、疲労度は \(M_1\)（区間内の最大値）。 - 最大値 \(M_1 > K\) のとき: 最も過酷な隣接ペア（値が \(M_1\) であるもの）をちょうど1つ回避するのが最適です。回避した後の疲労度は、残った要素の中での最大値、すなわち区間内で2番目に大きい値 \(M_2\) となります（要素が1つしかない場合は \(0\)）。

したがって、各クエリに対して必要な情報は、区間 \([l, r-1]\) における「最大値 \(M_1\)」と「2番目に大きい値 \(M_2\)」の2つだけです。

2. 素朴なアプローチとその限界

クエリごとに区間 \([l, r-1]\) を走査して最大値と2番目の最大値を求めると、1回のクエリに \(O(N)\) の時間がかかります。 最悪の場合、全体の計算量は \(O(NQ)\) となり、制約（\(N, Q \le 2 \times 10^5\)）のもとでは実行時間制限に間に合いません（TLE）。

また、イベント1によって途中で標高 \(A_p\) が更新されるため、事前に累積的な計算をしておくことも困難です。

3. セグメント木による高速化

「点更新」と「区間の情報の取得」を同時に高速に行うための代表的なデータ構造がセグメント木です。 セグメント木の各ノードに「最大値」と「2番目の最大値」のペアを持たせることで、区間クエリを \(O(\log N)\) で処理できるようになります。

---

アルゴリズム

セグメント木のノードとマージ演算

セグメント木の各ノードは以下の構造体 Node を持ちます。 - max1: 担当区間における最大値 - max2: 担当区間における2番目に大きい値

2つのノード a と b をマージして新しいノードを作る演算 op(a, b) は、以下のように定義できます。

1. a.max1 と b.max1 のうち、大きい方を新しい max1 とする。
2. 新しい max2 は、a.max1, a.max2, b.max1, b.max2 の4つの値のうち、全体で「2番目に大きい値」とする。

具体的には、以下のように実装できます。

Node op(Node a, Node b) {
    long long m1, m2;
    if (a.max1 >= b.max1) {
        m1 = a.max1;
        m2 = max(a.max2, b.max1); // aの最大値が一番大きいので、2番目は a.max2 か b.max1 のどちらか
    } else {
        m1 = b.max1;
        m2 = max(a.max1, b.max2); // bの最大値が一番大きいので、2番目は a.max1 か b.max2 のどちらか
    }
    return {m1, m2};
}

この演算は結合法則を満たし、単位元は {0, 0} となるため、セグメント木に乗せることができます。

クエリの処理

• イベント 1（更新）: \(A_p\) が \(v\) に変更されると、隣接する差分である \(d_{p-1}\) と \(d_p\) の最大2箇所が変化します。 セグメント木の該当する位置の値を更新します。
• イベント 2（取得）: \(l = r\) の場合は \(0\) を出力します。 そうでない場合、セグメント木を用いて区間 \([l, r-1]\) の総積（マージ結果）を取得します。 得られた結果の max1 が \(K\) 以下なら max1 を、\(K\) より大きいなら max2 を出力します。

---

計算量

• 時間計算量: \(O(N + Q \log N)\)

  • 初期構築: \(O(N)\)
  • イベント 1（更新）: 1回あたり \(O(\log N)\)
  • イベント 2（取得）: 1回あたり \(O(\log N)\)
  • 全体で \(Q\) 回のクエリを処理するため、十分高速に実行可能です。

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

  • 長さ \(N\) の配列と、同等のサイズを持つセグメント木を保持するため、メモリ制限にも余裕で収まります。

---

実装のポイント

• 半開区間に注意: AtCoder Library (ACL) の segtree の prod(l, r) は半開区間 \([l, r)\) のクエリを処理します。 チェックポイント \(l\) から \(r\) までの隣接ペアは \(d_l, d_{l+1}, \ldots, d_{r-1}\) です。 したがって、セグメント木に対して seg.prod(l, r) を呼び出すことで、ちょうどインデックス \(l\) から \(r-1\) までの要素の総積を正しく取得できます。

• 境界条件のハンドリング: \(p = 1\) のときは \(d_{p-1}\) は存在せず、\(p = N\) のときは \(d_p\) は存在しません。更新クエリの際は、インデックスが範囲内にあるかを適切に条件分岐で確認する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <atcoder/segtree>

using namespace std;

struct Node {
    long long max1;
    long long max2;
};

Node op(Node a, Node b) {
    long long m1, m2;
    if (a.max1 >= b.max1) {
        m1 = a.max1;
        m2 = max(a.max2, b.max1);
    } else {
        m1 = b.max1;
        m2 = max(a.max1, b.max2);
    }
    return {m1, m2};
}

Node e() {
    return {0, 0};
}

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

    int N, Q;
    long long K;
    if (!(cin >> N >> Q >> K)) return 0;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    vector<Node> init_d(N);
    for (int i = 1; i < N; ++i) {
        init_d[i] = {abs(A[i] - A[i + 1]), 0};
    }

    atcoder::segtree<Node, op, e> seg(init_d);

    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            int p;
            long long v;
            cin >> p >> v;
            A[p] = v;
            if (p > 1) {
                seg.set(p - 1, {abs(A[p - 1] - A[p]), 0});
            }
            if (p < N) {
                seg.set(p, {abs(A[p] - A[p + 1]), 0});
            }
        } else {
            int l, r;
            cin >> l >> r;
            if (l == r) {
                cout << 0 << "\n";
            } else {
                Node res = seg.prod(l, r);
                if (res.max1 <= K) {
                    cout << res.max1 << "\n";
                } else {
                    cout << res.max2 << "\n";
                }
            }
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。