自动搬运

查看原文

来自洛谷，原作者为

	x_angelkawaii_x **

搬运于2025-08-24 22:21:36，当前版本为作者最后更新于2020-05-05 14:53:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 子任务 $1$

按照题意模拟即可。

时间复杂度 $\mathcal{O}(q^3)$ ，期望得分 $5$ 分

• 子任务 $2$

在插入每个点时更新答案即可。

时间复杂度 $\mathcal{O}(q^2)$ ，期望得分 $15$ 分

• 子任务 $3$

注意到芙兰距离为曼哈顿距离+$v_{max(u,v)}$

因此插入点 $(x_i,y_i,v_i)$ 时查询该点与其余点的最大曼哈顿距离+$v_i$ 即可更新答案

将 $(x,y)$ 变为 $(x+y,x-y)$，最大曼哈顿距离被转化为最大切比雪夫距离。显然只有 $x,y$ 坐标最小和最大的四个点可能和 $i$ 的切比雪夫距离最大，枚举即可。

时间复杂度 $\mathcal{O}(q)$ ，期望得分 $35$ 分

• 子任务 $4$

有一点可能不能参与运算，因此需要记录 $i$ 与之前点的最大"芙兰距离"与次大"芙兰距离"。

记 '$i$ 与 $x(x<i)$ 的"芙兰距离"是 $w$' 为三元组 $(i,x,w)$，则查询忽略 $a$ 时的答案 即询问所有前两个数字不包含 $a$ 的三元组中，$w$ 的最大值是多少。

以 $i$ 为横坐标，$x$ 为纵坐标，那么不包含 $a$ 相当于去掉了两条直线。拆成四个矩形查询，可以使用 k-d tree 维护。

时间复杂度 $\mathcal{O}(q\sqrt{q})$，期望得分 $60$ 分

• 子任务 $5$

瓶颈在于 k-d tree ，所以我们想办法优化最后一步。

一个三元组 $(i,x,w)$ 对查询 $a$ 有影响，当且仅当 $i \neq a$ 且 $x \neq a$。所以插入三元组时将区间 $[1,x-1]$，$[x+1,i-1]$，$[i+1,n]$ 中的数字对 $w$ 取 $max$，查询时单点求值即可。使用线段树即可轻松维护。

时间复杂度 $\mathcal{O}(q\log q)$，期望得分 $100$ 分