概要

直線道路上を移動する \(N\) 台の山車すべてを収めるために必要な最小のフレーム幅を、運行計画の修正（\(Q\) 回）が行われるたびに求める問題です。各時点において、\(0\) 日目から \(D\) 日目までのうち、フレーム幅が最小となる日を特定する必要があります。

考察

1. フレーム幅の式を整理する

\(d\) 日目における山車 \(i\) の右端の座標を \(R_i(d)\)、左端の座標を \(L_i(d)\) とすると、 - \(R_i(d) = (X_i + L_i) + V_i \cdot d\) - \(L_i(d) = (X_i - L_i) + V_i \cdot d\) となります。ここで \(P_i = X_i + L_i, \ M_i = X_i - L_i\) と置くと、フレーム幅 \(F(d)\) は次のように表せます。 $\(F(d) = \max_{1 \le i \le N}(V_i \cdot d + P_i) - \min_{1 \le i \le N}(V_i \cdot d + M_i)\)$

さらに、\(\min(A_i) = -\max(-A_i)\) という性質を利用すると、 $\(F(d) = \max_{1 \le i \le N}(V_i \cdot d + P_i) + \max_{1 \le i \le N}(-V_i \cdot d - M_i)\)$ と書き換えられます。

2. 関数の性質（凸性）に注目する

\(V_i \cdot d + P_i\) は \(d\) に関する一次関数です。複数の一次関数の最大値をとって作られる関数（上側包絡線）は、数学的に凸関数になるという性質があります。 \(F(d)\) は「凸関数」と「別の凸関数」の和であるため、\(F(d)\) 自体も \(d\) に関して凸関数となります。

3. 効率的な最小値の探索

凸関数の最小値を求める場合、単純に全探索（\(0\) から \(D\) まで調べる）すると \(O(D)\) かかり、制約の \(D \le 10^9\) では間に合いません。 しかし、凸関数であれば「傾き（差分）」が単調に増加するため、二分探索（または三分探索）を用いて最小値を高速に求めることができます。

今回は離散的な値（整数日）を扱うため、「\(F(d+1) - F(d) \ge 0\) となる最小の \(d\)」を二分探索で探すことで、最小値を与える日を特定できます。

アルゴリズム

1. 初期データの管理: 各山車の \(V_i, P_i, M_i\) を配列で保持します。
2. 二分探索による最小値計算: 各バージョン（修正後）において、以下の手順で \(G_t\) を求めます。
   • 探索範囲を \([low, high] = [0, D-1]\) とする。
   • \(mid = (low + high) / 2\) について、\(F(mid)\) と \(F(mid+1)\) を比較する。
   • \(F(mid+1) \ge F(mid)\) ならば、最小値は \(mid\) 以下にあるので \(high = mid - 1\)。
   • そうでなければ、最小値は \(mid+1\) 以降にあるので \(low = mid + 1\)。
   • 最終的に見つかった \(d\) における \(F(d)\) が答え。
3. 修正の反映: \(Q\) 回の修正指示ごとに、該当する山車の \(V_i, P_i, M_i\) を更新し、再度二分探索を行います。

計算量

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

  • 1回の \(F(d)\) の計算に \(O(N)\) かかります。
  • 1つのバージョンにつき、二分探索で \(O(\log D)\) 回 \(F(d)\) を計算します。
  • バージョンは全部で \(Q+1\) 個あります。
  • 制約 \(N(Q+1) \le 5 \times 10^5\) かつ \(\log D \approx 30\) であるため、全体の計算回数は約 \(1.5 \times 10^7\) 程度となり、実行時間制限内に収まります。

• 空間計算量: \(O(N)\)

  • 山車 \(N\) 台分のパラメータを保持するメモリが必要です。

実装のポイント

• 高速化: \(F(d)\) の計算はボトルネックになるため、ループ内の処理を簡潔にします。

• 型: 座標やフレーム幅は非常に大きな値になる可能性があるため、C++では long long 型（64bit整数）を使用します。

• 境界条件: \(D=0\) の場合や、二分探索の範囲外（\(d=D\) が最小の場合など）に注意して実装します。”`

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem Analysis:
 * The frame width F(d) on day d is given by:
 * F(d) = max_i(X_i + V_i*d + L_i) - min_i(X_i + V_i*d - L_i)
 * Let P_i = X_i + L_i and M_i = X_i - L_i.
 * F(d) = max_i(V_i*d + P_i) - min_i(V_i*d + M_i)
 * Since min_i(A_i) = -max_i(-A_i), we have:
 * F(d) = max_i(V_i*d + P_i) + max_i(-V_i*d - M_i)
 * 
 * Both max_i(V_i*d + P_i) and max_i(-V_i*d - M_i) are the upper envelopes of linear functions,
 * which makes them convex functions of d. The sum of two convex functions is also convex.
 * Therefore, F(d) is a convex function on the discrete interval [0, D].
 * 
 * To find the minimum of a discrete convex function G = min_{0 <= d <= D} F(d), 
 * we can binary search for the point where the "derivative" F(d+1) - F(d) changes sign from negative to non-negative.
 * 
 * Complexity:
 * Each update changes one float. After each update, we need to find G_t.
 * Binary search on [0, D] takes log2(D) steps.
 * Each step evaluates F(d) twice, and each evaluation takes O(N) time.
 * Total complexity: O(Q * N * log(D)).
 * Given the constraint N(Q+1) <= 5 * 10^5 and log2(D) approx 30, the total number of operations
 * is roughly 30 * 2 * 5 * 10^5 = 3 * 10^7, which comfortably fits within the 2-second time limit.
 */

typedef long long ll;

// Function to calculate the frame width F(d) at day d
ll calculate_F(ll d, int N, const vector<ll>& v, const vector<ll>& p, const vector<ll>& m) {
    ll max_p_val = -8e18; // Sufficiently small value to initialize max search
    ll max_m_val = -8e18;
    for (int i = 0; i < N; ++i) {
        ll val_p = v[i] * d + p[i];
        ll val_m = -v[i] * d - m[i];
        if (val_p > max_p_val) max_p_val = val_p;
        if (val_m > max_m_val) max_m_val = val_m;
    }
    return max_p_val + max_m_val;
}

// Function to find the minimum frame width G_t for the current version
ll solve_for_version(int N, ll D, const vector<ll>& v, const vector<ll>& p, const vector<ll>& m) {
    if (D == 0) return calculate_F(0, N, v, p, m);
    
    ll low = 0, high = D - 1;
    ll best_d = D; // Initialize with the boundary value
    
    // Binary search for the first d such that F(d+1) >= F(d)
    while (low <= high) {
        ll mid = low + (high - low) / 2;
        if (calculate_F(mid + 1, N, v, p, m) >= calculate_F(mid, N, v, p, m)) {
            best_d = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return calculate_F(best_d, N, v, p, m);
}

int main() {
    // Fast I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    ll D;
    if (!(cin >> N >> D >> Q)) return 0;

    // Store parameters for each float
    vector<ll> v(N), p(N), m(N);
    for (int i = 0; i < N; ++i) {
        ll xi, vi, li;
        cin >> xi >> vi >> li;
        v[i] = vi;
        p[i] = xi + li;
        m[i] = xi - li;
    }

    // Version 0: Initial data
    cout << solve_for_version(N, D, v, p, m) << "\n";

    // Versions 1 to Q: Process each update
    for (int j = 0; j < Q; ++j) {
        int pj;
        ll aj, bj, cj;
        cin >> pj >> aj >> bj >> cj;
        --pj; // Convert 1-indexed float ID to 0-indexed vector index
        
        // Update float parameters
        v[pj] = bj;
        p[pj] = aj + cj;
        m[pj] = aj - cj;
        
        // Find and output the minimum frame width for the current version
        cout << solve_for_version(N, D, v, p, m) << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。