Official
E - 登山道の快適さ / Comfort of the Mountain Trail Editorial by admin
Claude 4.6 Opus (Thinking)概要
登山道上の隣接チェックポイント間の標高差に対して、点更新と区間クエリ（最大値、ただし最大値が閾値 \(K\) を超える場合は1つ除外可能）を高速に処理する問題。セグメント木で最大値・第2最大値を管理して解く。
考察
疲労度の計算を整理する
まず \(d_i = |A_i - A_{i+1}|\)（隣接標高差）を定義すると、区間 \([l, r]\) の疲労度は \(d_l, d_{l+1}, \ldots, d_{r-1}\) に対する操作で決まります。
- \(M_1 = \max(d_l, \ldots, d_{r-1})\) とする
- \(M_1 \le K\) なら答えは \(M_1\)
- \(M_1 > K\) なら、集合からちょうど1つの要素を除外して残りの最大値を最小化する
除外の最適戦略
「1つ除外して残りの最大値を最小化」するには、最大値 \(M_1\) を持つ要素を除外するのが最適です。除外後の最大値は：
- \(M_1\) の値を持つ要素が2個以上ある → 1つ除いても最大値は \(M_1\) のまま
- \(M_1\) の値を持つ要素がちょうど1個 → 除外後の最大値は第2最大値 \(M_2\)
素朴なアプローチの問題点
各クエリで区間を走査すると \(O(N)\) かかり、\(Q\) 回のクエリで \(O(NQ)\) となりTLEします。
解決策
セグメント木の各ノードに (最大値 \(M_1\), その出現回数 \(c_1\), 第2最大値 \(M_2\)) の3つ組を持たせることで、区間の情報を \(O(\log N)\) で取得できます。
アルゴリズム
前処理: \(d_i = |A_i - A_{i+1}|\)（\(i = 1, \ldots, N-1\)）を計算し、セグメント木を構築する。
セグメント木のノード情報: \((M_1, c_1, M_2)\)
- \(M_1\): 区間内の最大値
- \(c_1\): \(M_1\) の出現回数
- \(M_2\): \(M_1\) より真に小さい最大の値（存在しなければ \(-1\)）
ノードのマージ: 2つの子ノード \((a_{M1}, a_{c1}, a_{M2})\) と \((b_{M1}, b_{c1}, b_{M2})\) を統合：
- \(a_{M1} > b_{M1}\) → \(M_1 = a_{M1}\), \(c_1 = a_{c1}\), \(M_2 = \max(a_{M2}, b_{M1})\)
- \(a_{M1} < b_{M1}\) → \(M_1 = b_{M1}\), \(c_1 = b_{c1}\), \(M_2 = \max(b_{M2}, a_{M1})\)
- \(a_{M1} = b_{M1}\) → \(M_1 = a_{M1}\), \(c_1 = a_{c1} + b_{c1}\), \(M_2 = \max(a_{M2}, b_{M2})\)
イベント1（更新）: \(A_p\) を変更後、\(d_{p-1}\) と \(d_p\) を再計算してセグメント木を点更新。
イベント2（クエリ）: 区間 \([l, r-1]\) のノード情報 \((M_1, c_1, M_2)\) を取得し：
- \(l = r\) → 答えは \(0\)
- \(M_1 \le K\) → 答えは \(M_1\)
- \(M_1 > K\) かつ区間長1（\(r = l+1\)）→ 答えは \(0\)
- \(M_1 > K\) かつ \(c_1 \ge 2\) → 答えは \(M_1\)（除外しても最大値は変わらない）
- \(M_1 > K\) かつ \(c_1 = 1\) → 答えは \(\max(M_2, 0)\)
計算量
- 時間計算量: \(O((N + Q) \log N)\)（構築 \(O(N)\)、各クエリ・更新 \(O(\log N)\)）
- 空間計算量: \(O(N)\)（セグメント木のサイズ）
実装のポイント
セグメント木のサイズは \(N-1\) 個の要素（\(d_1, \ldots, d_{N-1}\)）に対して構築する。2冪に切り上げる。
空ノードを表す特別な値
(-1, 0, -1)を用意し、マージ時に片方が空なら他方をそのまま返す。\(A_p\) を変更すると \(d_{p-1}\) と \(d_p\) の最大2箇所が影響を受けるため、範囲チェックして両方更新する。
\(M_2\) が存在しない場合（\(-1\)）に備えて、最終出力時に \(\max(M_2, 0)\) とする（疲労度は非負）。
ソースコード
import sys
from math import inf
def main():
input_data = sys.stdin.buffer.read().split()
idx = 0
N = int(input_data[idx]); idx += 1
Q = int(input_data[idx]); idx += 1
K = int(input_data[idx]); idx += 1
A = [0] * (N + 1)
for i in range(1, N + 1):
A[i] = int(input_data[idx]); idx += 1
# d[i] = |A[i] - A[i+1]| for i = 1..N-1
# We need a segment tree on d[1..N-1] that supports:
# - point update
# - range query: given [l, r-1], find:
# 1) max of range (M1)
# 2) second max of range (M2) — the max after removing the element achieving M1
# More precisely: if M1 > K, we remove exactly one element to minimize the resulting max.
# The optimal strategy is to remove an element with value = M1.
# After removal, the max is the second largest value, i.e., max of all elements except
# one occurrence of M1. But if all elements equal M1, removing one still leaves M1
# (unless there's only one element).
#
# Actually, let's think more carefully:
# We want min over j of (max of S \ {j}).
# To minimize, we should remove the element with the largest d value.
# After removing the max element, the new max is:
# - If there are >= 2 elements with value = max, then still max.
# - If there's exactly 1 element with value = max, then second max.
#
# So we need: max1, max2 (first and second maximum), and count of max1.
# Segment tree storing (max1, count_of_max1, max2) for each node
# max2 is the largest value strictly less than max1, or -inf if none
sz = 1
while sz < (N - 1):
sz *= 2
# Each node: (max1, cnt1, max2)
EMPTY = (-1, 0, -1) # represents empty interval
tree = [EMPTY] * (2 * sz)
def make_leaf(val):
return (val, 1, -1)
def combine(a, b):
if a[0] == -1 and a[1] == 0:
return b
if b[0] == -1 and b[1] == 0:
return a
am1, ac1, am2 = a
bm1, bc1, bm2 = b
if am1 > bm1:
m1 = am1
c1 = ac1
m2 = max(am2, bm1)
elif am1 < bm1:
m1 = bm1
c1 = bc1
m2 = max(bm2, am1)
else:
m1 = am1
c1 = ac1 + bc1
m2 = max(am2, bm2)
return (m1, c1, m2)
# Build
d = [0] * (N) # d[i] for i=1..N-1, stored at d[i]
for i in range(1, N):
d[i] = abs(A[i] - A[i + 1])
for i in range(1, N):
tree[sz + i - 1] = make_leaf(d[i])
for i in range(sz - 1, 0, -1):
tree[i] = combine(tree[2 * i], tree[2 * i + 1])
def update(pos, val):
# pos is 1-indexed in d array
pos = pos - 1 + sz # 0-indexed in tree leaves
tree[pos] = make_leaf(val)
pos >>= 1
while pos >= 1:
tree[pos] = combine(tree[2 * pos], tree[2 * pos + 1])
pos >>= 1
def query(l, r):
# query d[l..r], 1-indexed
if l > r:
return EMPTY
l = l - 1 + sz
r = r - 1 + sz
res_l = EMPTY
res_r = EMPTY
while l <= r:
if l & 1:
res_l = combine(res_l, tree[l])
l += 1
if not (r & 1):
res_r = combine(tree[r], res_r)
r -= 1
l >>= 1
r >>= 1
return combine(res_l, res_r)
out = []
for _ in range(Q):
t = int(input_data[idx]); idx += 1
if t == 1:
p = int(input_data[idx]); idx += 1
v = int(input_data[idx]); idx += 1
A[p] = v
if p - 1 >= 1:
d[p - 1] = abs(A[p - 1] - A[p])
update(p - 1, d[p - 1])
if p + 1 <= N:
d[p] = abs(A[p] - A[p + 1])
update(p, d[p])
else:
l = int(input_data[idx]); idx += 1
r = int(input_data[idx]); idx += 1
if l == r:
out.append(0)
elif r == l + 1:
val = abs(A[l] - A[r])
if val <= K:
out.append(val)
else:
out.append(0)
else:
# query d[l..r-1]
m1, c1, m2 = query(l, r - 1)
if m1 <= K:
out.append(m1)
else:
# remove one element with value m1
if c1 >= 2:
out.append(m1)
else:
out.append(max(m2, 0))
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()
この解説は claude4.6opus-thinking によって生成されました。