SOl P11728(KTT)

KTT 做法。这里的变量可能和原题有一定不同。

以下令第 $i$ 个波特当前的移动速度为 $k_i$，当前时刻的位置为 $b_i$。初始 $k_i=0,b_i=a_i$。

首先离原点最远的显然就是 $b_i$ 最大或者 $b_i$ 最小的，这里只介绍 $b_i$ 最大的情况，$b_i$ 最小的情况只需要把初始位置和操作取相反数再求最大即可。

考虑第 $p$ 次操作和第 $p-1$ 次操作之间的 $\Delta t=t_p-t_{p-1}$ 秒中发生了什么，对于第 $i$ 个波特，显然是以 $k_i$ 的速度匀速移动了 $\Delta t$ 秒，有 $b_i\gets b_i+k_i\cdot \Delta t$，那就是在每次操作之前，所有 $b_i$ 都增加 $k_i\cdot \Delta t$。

现在需要支持以下三种操作：

然后这个 $k$ 和 $b$ 可以看成一次函数，第一个操作就是所有一次函数左移 $\Delta t$ 个单位，第二个操作就是修改其中一个一次函数的斜率，这个很像 KTT 的形式。

考虑用 KTT 做，每个节点维护三个值：$\max_k,\max_b,w$。$\max_k$ 和 $\max_b$ 表示当前 $b$ 值最大（零点时函数值最大）的一次函数的 $k$ 和 $b$，$w$ 就是阈值，即子树内的一次函数再左移 $w$ 单位之后 $\max_k,\max_b$ 会改变，如果 $\max$ 不会改变则 $w=\infty$，一个叶节点 $[i,i]$ 的 $\max_k=k_i,\max_b=b_i,w=\infty$。

对于 $\max_k,\max_b$ 这两个值，合并两个区间 $[l,mid],[mid+1,r]$ 是简单的，对于 $w$，则有 $w_{[l,r]}=\min(w_{[l,mid]},w_{[mid+1,r]})$，同时，如果 $[l,mid]$ 和 $[mid+1,r]$ 的函数 $f_1(x)=\max_{[l,mid],k}x+\max_{[l,mid],b}$ 和 $f_2(x)=\max_{[mid+1,r],k}x+\max_{[mid+1,r],b}$ 在 $x\ge0$ 有交点 $(p_x,p_y)$，那么 $\max_{[l,r],k},\max_{[l,r],b}$ 肯定会在 $p_x$ 处（或者前面）发生改变，因此还有 $w_{[l,r]}\gets \min(w_{[l,r]},p_x)$。

对于所有 $b_i$ 都增加 $k_i\cdot \Delta t$ 这个操作（全体左移 $t$ 格），维护懒标记 $lazy_{[l,r]}$ 表示 $[l,r]$ 的子树中函数需要左移 $lazy_{[l,r]}$ 格。修改一个节点时，如果需要左移 $p$ 格，则 $\max_b\gets k_i\cdot p$，同时 $w\gets w-p$，然后懒标记也同时修改一下就行了，在 $\tt command$ 时再下传。然后对于全体修改，如果 $\Delta t<w_{[1,n]}$ 就修改节点 $[1,n]$ 就可以，否则就重构子树，就是递归更新左右子树，令当前节点为 $[l,r]$，如果 $lazy_{[l,r]}+\Delta t$ 小于子节点的 $w$ 就继续递归更新，否则直接修改子节点并打上懒标记，然后 pushup。

pushdown 的时候应该是不用判是否超过阈值的，因为如果 $\Delta t<w_{[1,n]}$ 显然 $\Delta t$ 也小于其子节点的 $w$。

对于一次 $\tt command$ 操作，直接找到 $[pos,pos]$，然后逐个 pushup，更新 $\max_k,\max_b,w$ 就行了。

对于 $\tt query$ 操作，显然 $\max_{[1,n],b}$ 即为当前时刻答案。

复杂度应该是 $O(n\log^2 n)$（$O(n\log^3 n)$？）可以看下 KTT 论文（P52 浅谈函数最值的动态维护）。