まずはショートカットがないバージョンの問題を考えます。

このときクエリは、差の列 \(d_i = |A_i-A_{i+1}|\) に対する2点更新と区間max計算になるので、\(d\) をセグメントツリーで管理することで \(O((N+Q)\log N)\) で解くことができます。

元の問題を考えます。条件を整理すると「指定された区間の最大値が \(K\) 以下ならそれを出力、\(K\) より大きいなら2番目に大きな値を出力」となります。よって、2番目に大きな値を取得できるようなセグメントツリーを用いることでこの問題を \(O((N+Q)\log N)\) で解くことができます。

この他、「最大値とその index を取得できるセグメント木」を用い、まず区間 \([l,r]\) の最大値を取得したあと、それが \(K\) より大きければ区間 \([l,i),(i,r]\) にクエリを投げて2番目の最大値を求める、という方法もあります。

実装例 (C++)

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

using X = pair<int, int>;
X xx(X x, X y){
  int a1, a2;
  if(x.first > y.first){
    a1 = x.first;
    a2 = max(x.second, y.first);
  }else{
    a1 = y.first;
    a2 = max(x.first, y.second);
  }
  return {a1, a2};
}
X xid(){return {0, 0};}


int main(){
  int n, q, k;
  cin >> n >> q >> k;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<X> d(n-1);
  for(int i=0; i<n-1; i++){
    d[i]={abs(a[i+1]-a[i]), 0};
  }
  atcoder::segtree<X,xx,xid>seg(d);

  for(int i=0; i<q; i++){
    int t;
    cin >> t;
    if(t == 1){
      int p, v;
      cin >> p >> v;
      p--;
      a[p] = v;
      if(p != 0){
        seg.set(p-1, {abs(a[p]-a[p-1]), 0});
      }
      if(p != n-1){
        seg.set(p, {abs(a[p+1]-a[p]), 0});
      }
    }else{
      int l, r;
      cin >> l >> r;
      l--, r--;
      auto [a1, a2] = seg.prod(l, r);
      if(a1 <= k){
        cout << a1 << endl;
      }else{
        cout << a2 << endl;
      }
    }
  }
}

実装例 (Python)

from atcoder.segtree import SegTree

def xx(x, y):
  if x[0] > y[0]:
    return (x[0], max(y[0], x[1]))
  else:
    return (y[0], max(x[0], y[1]))

N, Q, K = map(int, input().split())
A = list(map(int, input().split()))
D = [(abs(A[i+1] - A[i]), 0) for i in range(N-1)]

seg = SegTree(xx, (0,0), D)
for _ in range(Q):
  t, *q = map(int, input().split())
  if t == 1:
    p, v = q
    p -= 1
    A[p] = v
    if p != 0:
      seg.set(p-1, (abs(A[p]-A[p-1]), 0))
    if p != N-1:
      seg.set(p, (abs(A[p+1]-A[p]), 0))
  else:
    l, r = q
    l -= 1
    r -= 1
    a1, a2 = seg.prod(l, r)
    if a1 <= K:
      print(a1)
    else:
      print(a2)