Triangles 题解

EasonLiang · 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}？