自动搬运

查看原文

来自洛谷，原作者为

	EasonLiang **

搬运于2025-08-24 23:11:47，当前版本为作者最后更新于2025-01-26 15:17:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

每个剖分形成的三角形，将多边形的边分为了三组。将这三组边按顺时针方向记为 $S, T, U$ 三个集合，那么考虑从某个集合中的边进入，再从另一集合中的边走出，穿过该三角形所造成的贡献：

• 以 $S$ 中的边为入边、$T$ 中的边为出边，穿过该三角形时进行了一次左转；
• 以 $S$ 中的边为入边、$U$ 中的边为出边，穿过该三角形时进行了一次右转；
• 以 $T$ 中的边为入边、$U$ 中的边为出边，穿过该三角形时进行了一次左转；
• 以 $T$ 中的边为入边、$S$ 中的边为出边，穿过该三角形时进行了一次右转；
• 以 $U$ 中的边为入边、$S$ 中的边为出边，穿过该三角形时进行了一次左转；
• 以 $U$ 中的边为入边、$T$ 中的边为出边，穿过该三角形时进行了一次右转。

那么我们只需对于每个三角形计算贡献即可。统计贡献可以通过前缀和优化做到线性。

接下来我们只需考虑如何线性求出每个三角形的顶点编号。

首先我们求出以 $1, n$ 为其中两个顶点的三角形的剩下一个顶点 $x$。不难发现，$x$ 是三角剖分中与 $1$ 连边的顶点（特别地，我们认为 $u$ 与 $(u \bmod n) + 1$ 之间也有连边）中编号第二大的点，也是与 $n$ 连边的顶点中编号第二小的点。

接下来，我们考虑以 $1, x$ 为其中两个顶点、以 $x, n$ 为其中两个顶点，且顶点不为 $1, x, n$ 三个编号的三角形。

• 对于其中两个顶点为 $1, x$ 的三角形，它的剩下一个顶点 $y$ 是与 $x$ 连边的顶点中编号第二小的顶点；
• 对于其中两个顶点为 $x, n$ 的三角形，它的剩下一个顶点 $z$ 是与 $x$ 连边的顶点中编号第二大的顶点。

然后我们可以继续递归考虑以 $1, y$、$y, x$、$x, z$、$z, n$ 为其中两个顶点的三角形。不难证明这样一定可以不重不漏地遍历所有三角形。而递归的过程只需要知道与每个 $u$ 连接的顶点中编号次大/次小的顶点，这个显然可以线性求出。

总时间复杂度 $O(n)$，std 最大点跑了 150ms 不到。

Bonus: 如何在线性时间内求出 $\sum_{u \neq v} v l^2_{u, v}$ 与 $\sum_{u \neq v} v r^2_{u, v}$？