概要

各バージョンについて、日付 \(d\) を \(0 \le d \le D\) の整数から選んだときのフレーム幅 \(F_t(d)\) の最小値を求めます。

ポイントは、\(F_t(d)\) が \(d\) に関して凸な関数になるため、全日付を試さずに二分探索で最小値を探せることです。

考察

日付 \(d\) において、山車 \(i\) が占有する区間は

\([X_i + V_i d - L_i,\ X_i + V_i d + L_i]\)

です。

すべての山車を収めるために必要なフレーム幅は、

\(F(d) = \max_i (X_i + V_i d + L_i) - \min_i (X_i + V_i d - L_i)\)

です。

ここで、

• 右端の最大値
  \(R(d) = \max_i (X_i + V_i d + L_i)\)
• 左端の最小値
  \(S(d) = \min_i (X_i + V_i d - L_i)\)

とおくと、

\(F(d) = R(d) - S(d)\)

です。

各山車について、\(X_i + V_i d + L_i\) や \(X_i + V_i d - L_i\) は \(d\) の一次関数です。

一次関数の最大値である \(R(d)\) は凸関数になります。
また、一次関数の最小値である \(S(d)\) は凹関数なので、\(-S(d)\) は凸関数です。

したがって、

\(F(d) = R(d) + (-S(d))\)

は凸関数になります。

整数上の凸関数は、値が

• 最初は減少し、
• どこかで最小になり、
• その後増加する

という形になります。つまり、単峰性を持ちます。

そのため、\(F(d)\) の最小値は二分探索で求められます。

素朴にすべての日付 \(d = 0, 1, \dots, D\) を試すと、\(D\) は最大 \(10^9\) なので間に合いません。

一方、ある日付 \(d\) に対する \(F(d)\) は、全山車を一度見ることで \(O(N)\) で計算できます。
これを二分探索で \(O(\log D)\) 回行えば、1 バージョンあたり \(O(N \log D)\) で求められます。

制約に \(N(Q+1) \le 5 \times 10^5\) があるため、全バージョンに対してこの方法を行っても十分間に合います。

アルゴリズム

各バージョンについて、次の処理を行います。

1. \(F(d)\) を計算する関数

日付 \(d\) が与えられたとき、全山車について

• 右端 \(X_i + V_i d + L_i\)
• 左端 \(X_i + V_i d - L_i\)

を計算します。

その最大右端と最小左端を求め、

\(F(d) = \max_i (X_i + V_i d + L_i) - \min_i (X_i + V_i d - L_i)\)

を返します。

2. 凸関数の最小値を二分探索する

探索範囲を \([0, D]\) とします。

中央を \(mid\) として、\(F(mid)\) と \(F(mid+1)\) を比較します。

• \(F(mid) \le F(mid+1)\) の場合
  \(mid\) より右では増加方向に向かっているため、最小値は \([lo, mid]\) にあります。
• \(F(mid) > F(mid+1)\) の場合
  まだ右に行くと値が小さくなるため、最小値は \([mid+1, hi]\) にあります。

これを \(lo = hi\) になるまで繰り返します。

最終的な \(lo\) が最小値を取る日付なので、\(F(lo)\) を出力します。

3. 更新処理

各修正では、山車 \(P_j\) の

• 初期座標
• 速度
• 半幅

を新しい値に置き換えます。

その後、再び上記の二分探索で答えを求めます。

計算量

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

ただし、制約より \(N(Q+1) \le 5 \times 10^5\) なので、全体として十分高速です。

実装のポイント

• 座標や速度、\(V_i \cdot d\) は大きくなるため、long long を使います。

• 二分探索中に mid + 1 を参照しますが、lo < hi のときだけ行うため、mid + 1 <= hi <= D となり範囲外にはなりません。

• 更新は配列 X, V, L の該当要素を書き換えるだけでよいです。

  ソースコード

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

using ll = long long;

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

    int N, Q;
    ll D;
    cin >> N >> D >> Q;

    vector<ll> X(N), V(N), L(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> V[i] >> L[i];
    }

    auto calc = [&](ll d) -> ll {
        ll mx = LLONG_MIN;
        ll mn = LLONG_MAX;
        for (int i = 0; i < N; i++) {
            ll c = X[i] + V[i] * d;
            mx = max(mx, c + L[i]);
            mn = min(mn, c - L[i]);
        }
        return mx - mn;
    };

    auto solve = [&]() -> ll {
        ll lo = 0, hi = D;
        while (lo < hi) {
            ll mid = (lo + hi) / 2;
            if (calc(mid) <= calc(mid + 1)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return calc(lo);
    };

    cout << solve() << '\n';

    for (int j = 0; j < Q; j++) {
        int P;
        ll A, B, C;
        cin >> P >> A >> B >> C;
        --P;
        X[P] = A;
        V[P] = B;
        L[P] = C;
        cout << solve() << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。