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 浅谈函数最值的动态维护）。

UOJ Submission