Overview

For each version, we find the minimum value of the frame width \(F_t(d)\) when the date \(d\) is chosen as an integer from \(0 \le d \le D\).

The key point is that \(F_t(d)\) is a convex function with respect to \(d\), so we can find the minimum using binary search without trying all dates.

Analysis

On date \(d\), the interval occupied by float \(i\) is

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

The frame width required to contain all floats is

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

Here, let us define:

• Maximum of the right endpoints
  \(R(d) = \max_i (X_i + V_i d + L_i)\)
• Minimum of the left endpoints
  \(S(d) = \min_i (X_i + V_i d - L_i)\)

Then,

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

For each float, \(X_i + V_i d + L_i\) and \(X_i + V_i d - L_i\) are linear functions of \(d\).

\(R(d)\), being the maximum of linear functions, is a convex function.
Also, \(S(d)\), being the minimum of linear functions, is a concave function, so \(-S(d)\) is convex.

Therefore,

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

is a convex function.

A convex function over integers has values that:

• First decrease,
• Reach a minimum somewhere,
• Then increase.

In other words, it is unimodal.

Thus, the minimum of \(F(d)\) can be found using binary search.

Naively trying all dates \(d = 0, 1, \dots, D\) would be too slow since \(D\) can be up to \(10^9\).

On the other hand, for a given date \(d\), \(F(d)\) can be computed in \(O(N)\) by scanning all floats once.
Doing this \(O(\log D)\) times via binary search gives \(O(N \log D)\) per version.

Since the constraint guarantees \(N(Q+1) \le 5 \times 10^5\), applying this method across all versions is fast enough.

Algorithm

For each version, perform the following steps.

1. Function to compute \(F(d)\)

Given a date \(d\), for all floats compute:

• Right endpoint: \(X_i + V_i d + L_i\)
• Left endpoint: \(X_i + V_i d - L_i\)

Find the maximum right endpoint and the minimum left endpoint, and return

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

2. Binary search for the minimum of the convex function

Set the search range to \([0, D]\).

Let \(mid\) be the midpoint, and compare \(F(mid)\) with \(F(mid+1)\).

• If \(F(mid) \le F(mid+1)\):
  The function is increasing to the right of \(mid\), so the minimum lies in \([lo, mid]\).
• If \(F(mid) > F(mid+1)\):
  The function is still decreasing to the right, so the minimum lies in \([mid+1, hi]\).

Repeat until \(lo = hi\).

The final \(lo\) is the date that achieves the minimum, so output \(F(lo)\).

3. Update processing

For each modification, replace float \(P_j\)’s

• Initial position
• Velocity
• Half-width

with the new values.

Then, find the answer again using the binary search described above.

Complexity

• Time complexity: \(O((Q+1)N\log D)\)
• Space complexity: \(O(N)\)

Since the constraint guarantees \(N(Q+1) \le 5 \times 10^5\), this is fast enough overall.

Implementation Notes

• Coordinates, velocities, and \(V_i \cdot d\) can become large, so use long long.

• During binary search, we access mid + 1, but this is only done when lo < hi, ensuring mid + 1 <= hi <= D, so it never goes out of range.

• Updates only require overwriting the corresponding elements of the arrays X, V, L.

  Source Code

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

---

This editorial was generated by gpt-5.5-xhigh.