最小化する関数 \(F_t(d)\) は下に凸な関数です。したがって、三分探索を用いて最小値を計算することができます。

\(F_t(d)\) の計算を愚直に行い \(O(N)\) 時間かけても全体で \(O(NQ\log D)\) 時間となり、\(N(Q+1) \le 5\times 10^5\) より実行時間制限に間に合います。

実装例(Python3)

import sys

input = sys.stdin.readline

n, d, q = map(int, input().split())
x = [0] * n
v = [0] * n
l = [0] * n
for i in range(n):
    x[i], v[i], l[i] = map(int, input().split())


def val():
    ans = float("inf")

    def calc(day):
        nonlocal ans
        min_val = float("inf")
        max_val = -float("inf")
        for i in range(n):
            center = x[i] + v[i] * day
            max_val = max(max_val, center + l[i])
            min_val = min(min_val, center - l[i])
        res = max_val - min_val
        ans = min(ans, res)
        return res

    le, ri = 0, d
    while ri - le > 2:
        lle = (2 * le + ri) // 3
        rri = (le + 2 * ri) // 3
        if calc(lle) < calc(rri):
            ri = rri
        else:
            le = lle
    for day in range(le, ri + 1):
        calc(day)
    return ans


print(val())
for _ in range(q):
    p, a, b, c = map(int, input().split())
    p -= 1
    x[p], v[p], l[p] = a, b, c
    print(val())