简要题意
给定平面上 \(n\) 个点和 \(m\) 条边,构成了 \(p\) 个多边形(我们不关心平面上多边形之外的部分),每一个多边形都有一个颜色,颜色总数为 \(c\);相邻的多边形可以通过相邻的边互达,边有边权,如果边权为 \(-1\) 则该边不能通过,保证任意两个多边形之间存在唯一路径互达;称两个多边形的距离为两个多边形之间的路径上所有边的边权之和。现在会进行 \(t\) 次操作,每一次操作会修改一个多边形的颜色,你需要在开始及每一次操作后回答所有同色的多边形对中,距离最小的一对的距离。
数据访问:\(c,p,t \le 1.2\times 10^4;n,m\le 1.2 \times 10^5\)。
分析
首先考虑怎么刻画一个多边形。
因为一条边关系两个多边形,这是无法用一个信息维护的,所以我们把一条边拆成两个点,一个维护顺时针方向的多边形(我们称为下边),另一个维护逆时针方向上的多边形(我们称为上边)。
我们可以考虑对每一个点的所有相邻的点进行极角排序,这样我们就可以统一处理顺序(顺时针)。然后我们对每一个点进行处理,对于排序后相邻的两条边,我们呢把第一条边的下边和第二条边的上边合并起来(使用并查集即可),可以证明这样后同一个多边形的边都在同一个并查集中。
之后我们就按照题意建边,会得到一棵树。然后考虑怎么回答询问。树上路径问题,考虑点分治,维护当前块上每一种颜色的点到重心的距离,前两个就是答案;实现上可以开 \(c+1\) 个堆,其中 \(c\) 个堆维护每一种颜色的距离,最后一个堆维护每一个颜色的答案。时间复杂度和块大小有关,也就是 \(O(n\log ^2 n)\)。
考虑怎么修改,考虑点分树的性质:树高为 \(O(\log n)\)。所以可以暴力修改,单次修改是 \(O(\log n)\),时间复杂度为 \(O(n \log^2 n)\)。
综上,时间复杂度为 \(O(n \log^2 n)\)。