Overview

This problem requires efficiently computing the “maximum value” and “second largest value” of differences between adjacent elements in a specified interval, while performing element updates (point updates) on the array.

To efficiently handle value updates and range queries, we use a Segment Tree.

---

Analysis

1. Rephrasing the Problem

Let \(d_i = |A_i - A_{i+1}|\) denote the absolute difference in elevation between checkpoints \(i\) and \(i+1\). When a hiker walks through the interval \([l, r]\), the set of elevation differences to consider is \(S = \{d_l, d_{l+1}, \ldots, d_{r-1}\}\).

The fatigue experienced by Aoki can be summarized as follows: - When \(l = r\): There are no adjacent pairs, so the fatigue is \(0\). - When the maximum \(M_1 \le K\): No avoidance is performed, so the fatigue is \(M_1\) (the maximum value in the interval). - When the maximum \(M_1 > K\): It is optimal to avoid exactly one of the most strenuous adjacent pairs (those with value \(M_1\)). After avoidance, the fatigue equals the maximum value among the remaining elements, which is the second largest value \(M_2\) in the interval (or \(0\) if there is only one element).

Therefore, the only information needed for each query is the “maximum value \(M_1\)” and the “second largest value \(M_2\)” in the interval \([l, r-1]\).

2. Naive Approach and Its Limitations

If we scan the interval \([l, r-1]\) for each query to find the maximum and second maximum, each query takes \(O(N)\) time. In the worst case, the total computation is \(O(NQ)\), which will not fit within the time limit (TLE) under the constraints (\(N, Q \le 2 \times 10^5\)).

Additionally, since Event 1 updates the elevation \(A_p\) during processing, it is difficult to precompute cumulative information.

3. Speeding Up with a Segment Tree

A representative data structure for simultaneously handling “point updates” and “range information retrieval” efficiently is the Segment Tree. By storing a pair of “maximum value” and “second largest value” in each node of the segment tree, range queries can be processed in \(O(\log N)\).

---

Algorithm

Segment Tree Node and Merge Operation

Each node of the segment tree holds the following structure Node: - max1: The maximum value in the responsible interval - max2: The second largest value in the responsible interval

The operation op(a, b) that merges two nodes a and b to create a new node is defined as follows:

1. The larger of a.max1 and b.max1 becomes the new max1.
2. The new max2 is the “second largest value” among the four values a.max1, a.max2, b.max1, b.max2.

Specifically, it can be implemented as follows:

Node op(Node a, Node b) {
    long long m1, m2;
    if (a.max1 >= b.max1) {
        m1 = a.max1;
        m2 = max(a.max2, b.max1); // Since a's max is the largest, the second is either a.max2 or b.max1
    } else {
        m1 = b.max1;
        m2 = max(a.max1, b.max2); // Since b's max is the largest, the second is either a.max1 or b.max2
    }
    return {m1, m2};
}

This operation satisfies the associative property, and the identity element is {0, 0}, so it can be used with a segment tree.

Query Processing

• Event 1 (Update): When \(A_p\) is changed to \(v\), up to 2 positions—the adjacent differences \(d_{p-1}\) and \(d_p\)—may change. Update the corresponding positions in the segment tree.
• Event 2 (Retrieval): If \(l = r\), output \(0\). Otherwise, use the segment tree to obtain the aggregate (merge result) of the interval \([l, r-1]\). If the resulting max1 is at most \(K\), output max1; if it is greater than \(K\), output max2.

---

Complexity

• Time Complexity: \(O(N + Q \log N)\)

  • Initial construction: \(O(N)\)
  • Event 1 (Update): \(O(\log N)\) per operation
  • Event 2 (Retrieval): \(O(\log N)\) per operation
  • Since we process \(Q\) queries in total, this runs sufficiently fast.

• Space Complexity: \(O(N)\)

  • We maintain an array of length \(N\) and a segment tree of equivalent size, which comfortably fits within the memory limit.

---

Implementation Notes

• Be careful with half-open intervals: The AtCoder Library (ACL) segtree’s prod(l, r) processes queries on the half-open interval \([l, r)\). The adjacent pairs from checkpoint \(l\) to \(r\) are \(d_l, d_{l+1}, \ldots, d_{r-1}\). Therefore, calling seg.prod(l, r) on the segment tree correctly retrieves the aggregate of elements from index \(l\) to \(r-1\).

• Handling boundary conditions: When \(p = 1\), \(d_{p-1}\) does not exist, and when \(p = N\), \(d_p\) does not exist. During update queries, you need to properly check with conditional branches whether the index is within the valid range.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.