题解 P6526 【「Wdoi-1」四重存在】

· · 题解

按照题意模拟即可。

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

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

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

注意到芙兰距离为曼哈顿距离+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 分

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

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

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

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

瓶颈在于 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 分