E - 登山道の快適さ / Comfort of the Mountain Trail 解説 by admin
gemini-3.5-flash-thinking概要
この問題は、配列の要素更新（イベント 1）と、指定された区間における「隣接する要素の差の絶対値」の最大値および2番目に大きい値を求めるクエリ（イベント 2）を高速に処理する問題です。
値の更新と区間クエリを効率的に行うために、セグメント木（Segment Tree） を用いて解くことができます。
考察
1. 疲労度の定義の整理
隣接するチェックポイントの標高差の絶対値を \(d_i = |A_i - A_{i+1}|\) とします。登山者が区間 \([l, r]\) を歩くとき、考慮すべき標高差の集合は \(S = \{d_l, d_{l+1}, \ldots, d_{r-1}\}\) です。この集合の要素数を \(M\) とします（\(M = r - l\)）。
問題文のルールを整理すると、以下のようになります。 - \(l = r\) のとき（\(S\) が空）、疲労度は \(0\)。 - \(l < r\) のとき、\(S\) の最大値を \(M_1\) とする。 - \(M_1 \le K\) ならば、疲労度は \(M_1\)。 - \(M_1 > K\) ならば、要素をちょうど 1 つ回避（削除）できる。 - 疲労度を最小にするためには、最も大きい値である \(M_1\) を削除するのが最適です。 - \(M_1\) を削除した後に残る値の最大値は、元の集合 \(S\) における 「2番目に大きい値」\(M_2\) になります。 - ただし、要素数が 1 つ（\(r = l + 1\)）の場合、唯一の要素を削除すると何も残らないため、疲労度は \(0\) となります。
したがって、各クエリで求めるべきものは、区間 \([l, r-1]\) における 「最大値 \(M_1\)」 と 「2番目に大きい値 \(M_2\)」 の 2 つです。
2. ナイーブ（素朴）な方法とその限界
クエリごとに区間 \([l, r-1]\) を走査して最大値と2番目の値を求めると、1回のクエリに \(O(N)\) の時間がかかります。最悪の場合、全体の計算量が \(O(QN)\) となり、 \(N, Q \le 2 \times 10^5\) の制約下では実行時間制限（TLE）になってしまいます。
また、イベント 1 によって標高が更新されるため、事前に累積的な計算をしておくことも困難です。
3. セグメント木による高速化
「点更新」と「区間クエリ」を同時かつ高速に行うデータ構造として セグメント木 が適しています。 通常のセグメント木は区間の最大値のみを保持しますが、ノードに持たせる情報を工夫することで「最大値」と「2番目に大きい値」の双方を同時に管理できます。
アルゴリズム
セグメント木の設計
セグメント木の各ノードに、その区間における (最大値, 2番目に大きい値) のペアを保持させます。
情報のマージ方法
2つの子ノードの情報をマージして、親ノードの情報を計算する方法を考えます。 左の子の情報を \((l_1, l_2)\)、右の子の情報を \((r_1, r_2)\) とします（ここで \(l_1 \ge l_2, r_1 \ge r_2\) とします）。
マージ後の最大値 \(m_1\) と2番目に大きい値 \(m_2\) は、以下のように \(O(1)\) で求まります。
- \(l_1 > r_1\) の場合
- 最大値は左側にあるので、\(m_1 = l_1\) となります。
- 2番目に大きい値候補は、左側の2番目 \(l_2\) と、右側の最大値 \(r_1\) です。したがって、\(m_2 = \max(l_2, r_1)\) となります。
- \(l_1 \le r_1\) の場合
- 最大値は右側にあるので、\(m_1 = r_1\) となります。
- 2番目に大きい値候補は、左側の最大値 \(l_1\) と、右側の2番目 \(r_2\) です。したがって、\(m_2 = \max(l_1, r_2)\) となります。
このマージ処理を用いることで、セグメント木の構築・更新・クエリのすべてを通常のセグメント木と同様の計算量で行うことができます。
クエリの処理手順
- 初期化: 隣接差の配列 \(d\)（長さ \(N-1\)）を構築し、それをもとにセグメント木を初期化します。
- イベント 1（更新）:
チェックポイント \(p\) の標高が \(v\) に変更されます。これによって影響を受ける隣接差は \(d_{p-1} = |A_{p-1} - A_p|\) と \(d_p = |A_p - A_{p+1}|\) の最大 2 箇所のみです。これらを再計算し、セグメント木を更新（
update）します。 - イベント 2（取得）:
区間 \([l, r]\) が与えられたとき：
- \(l = r\) の場合は、直ちに
0を出力します。 - \(l < r\) の場合は、セグメント木を用いて区間 \([l, r-1]\) の
(M_1, M_2)を取得します。- \(M_1 \le K\) ならば \(M_1\) を出力。
- \(M_1 > K\) ならば \(M_2\) を出力。
- \(l = r\) の場合は、直ちに
計算量
時間計算量:
- 初期構築: \(O(N)\)
- イベント 1（更新）: \(O(\log N)\)（高々 2 箇所のセグメント木更新）
- イベント 2（クエリ）: \(O(\log N)\)
- 全体時間計算量: \(O(N + Q \log N)\) \(N, Q \le 2 \times 10^5\) であるため、制限時間内に余裕を持って実行が可能です。
空間計算量: \(O(N)\)
- 長さ \(N-1\) のセグメント木を保持するために \(O(N)\) のメモリを使用します。
実装のポイント
非再帰セグメント木（1次元配列形式）の利用: Pythonでは再帰呼び出しのオーバーヘッドが大きいため、非再帰（ボトムアップ）形式のセグメント木を実装することで実行時間を大幅に削減できます。提供されたコードはこの方針で実装されており、非常に高速に動作します。
境界条件のハンドリング: \(p\) の更新時に \(p-1\) や \(p\) が配列の範囲外（\(0\) 未満や \(N-1\) 以上）にならないよう、
if p > 0:などの条件分岐で適切にガードしています。高速な入出力: クエリ数が多いため、
sys.stdin.readで入力を一括で読み込み、sys.stdout.writeで一括出力することで、入出力ボトルネックを回避しています。ソースコード
import sys
def solve():
input = sys.stdin.read
data = input().split()
if not data:
return
N = int(data[0])
Q = int(data[1])
K = int(data[2])
A = [int(x) for x in data[3:3+N]]
seg_n = N - 1
tree_max1 = [0] * (2 * seg_n)
tree_max2 = [0] * (2 * seg_n)
for i in range(seg_n):
tree_max1[seg_n + i] = abs(A[i] - A[i+1])
for i in range(seg_n - 1, 0, -1):
left = 2 * i
right = left + 1
l1, l2 = tree_max1[left], tree_max2[left]
r1, r2 = tree_max1[right], tree_max2[right]
if l1 > r1:
tree_max1[i] = l1
tree_max2[i] = l2 if l2 > r1 else r1
else:
tree_max1[i] = r1
tree_max2[i] = l1 if l1 > r2 else r2
def update(pos, val):
idx = pos + seg_n
tree_max1[idx] = val
idx >>= 1
while idx > 0:
left = 2 * idx
right = left + 1
l1, l2 = tree_max1[left], tree_max2[left]
r1, r2 = tree_max1[right], tree_max2[right]
if l1 > r1:
tree_max1[idx] = l1
tree_max2[idx] = l2 if l2 > r1 else r1
else:
tree_max1[idx] = r1
tree_max2[idx] = l1 if l1 > r2 else r2
idx >>= 1
def query(left, right):
m1, m2 = 0, 0
left += seg_n
right += seg_n
while left < right:
if left & 1:
l1, l2 = m1, m2
r1, r2 = tree_max1[left], tree_max2[left]
if l1 > r1:
m1 = l1
m2 = l2 if l2 > r1 else r1
else:
m1 = r1
m2 = l1 if l1 > r2 else r2
left += 1
if right & 1:
right -= 1
l1, l2 = m1, m2
r1, r2 = tree_max1[right], tree_max2[right]
if l1 > r1:
m1 = l1
m2 = l2 if l2 > r1 else r1
else:
m1 = r1
m2 = l1 if l1 > r2 else r2
left >>= 1
right >>= 1
return m1, m2
out = []
idx = 3 + N
for _ in range(Q):
t = int(data[idx])
if t == 1:
p = int(data[idx+1]) - 1
v = int(data[idx+2])
A[p] = v
if p > 0:
update(p - 1, abs(A[p-1] - A[p]))
if p < N - 1:
update(p, abs(A[p] - A[p+1]))
idx += 3
else:
l = int(data[idx+1]) - 1
r = int(data[idx+2]) - 1
if l == r:
out.append(0)
else:
m1, m2 = query(l, r)
if m1 <= K:
out.append(m1)
else:
out.append(m2)
idx += 3
sys.stdout.write('\n'.join(map(str, out)) + '\n')
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。