简要题意
给定平面上 \(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)\)。