P11757 [COTS 2014] 城市建设 / GRAD 题解

zrl123456 · 2025-11-14 09:00:07 · 题解

:::::info[闲话] LCA Project 几乎全机房人都被这道题肘飞了…… ::::: :::::info[题目基本信息] 考察：倍增（省选/NOI-）。
题目简介：
一个平面上初始时有两个点，坐标给定，且两点间有一条道路，长度为两点的欧几里得距离。
现在你要进行 n 次操作，操作分为两种：

1. 新增一个点，坐标为 (x,y)，同时会向 u,v 两点连边，长度也为欧几里得距离，但保证 u,v 两点已有边相连。
2. 查询 u,v 间最短路。

数据范围：

• 1\le n\le 10^5
• 0\le x,y\le 10^6
• 保证操作的点都存在，且两两坐标不相同。
  ::::: 这个题一个观察是如果直接跑最短路那么复杂度是不可接受的，一个考虑是通过某种方式把树建出来然后倍增跳求 LCA。
  显然如果直接对点是无法建树的，同时也无法删去任何一条边，但是我们观察到连边方式很特别，所以我们考虑对所连的边建树。
  具体地，每次连的边 (x,u),(x,v) 会和原来的边 (u,v) 形成一个三角形，所以我们考虑令 (x,u) 和 (x,v) 分别和 (u,v) 连边，容易发现最终连出来的就是一棵树。（为方便区分原来的边叫做原图边，后来建树用的边叫做建树边）
  :::::success[证明] 初始时有一条原图边和 0 条建树边，每次 1 操作会增加 2 条原图边和 2 条建树边，同时该图容易归纳证明一直联通，故该图一直为树。
  ::::: 由于本题中的边权都是欧几里得距离，他是两点间的最短距离，那么一个观察就是 u 到 v 走的路径一定是 u 新增时所连的原图边和 v 的新增时所连的原图边在树上的路径，同时由于发现 u 和 v 的分别的这两条新增时所连的原图边在树上共用父亲，故取哪条原图边效果均相同。
  实现上，我们可以对每个点存储两条新增时所连的原图边和坐标，对于每条原图边记录所连的两个点（可以使用指针）、在树上的深度以及树上的倍增数组，对于倍增数组的每一层我们都维护将会跳到的原图边（同样用指针）以及一矩阵表示跳的边和将会跳到的原图边的分别的任意一个端点间的距离，这个预处理也容易维护，倍增查询也是板子，不过有几个需要注意的点：
• 在两个原图边一起往上跳跳到即将相遇时，先别急着跳完，这时有可能两个点已经有公共端点了，记得把它算到贡献里。
• 如果你使用了指针，那么在用的时候一定要注意不要访问 NULL 指针内的元素，以及在别的函数内修改指针时可能会需要再次求指针，当然了如果你不想用指针后面会给一份 KSCD_ 的无指针实现方式。

结束。
时空复杂度均为 \Theta(n\log n)。

code（指针）
code（无指针）（这一份里有 freopen，是赛时代码）