当前位置: 首页 > news >正文

跨越国度 解题报告

简要题意

给定平面上 \(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)\)

http://www.hskmm.com/?act=detail&tid=25560

相关文章:

  • 手写Promise核心代码
  • 手动数据库分库分片策略
  • 大数据分析公司季度业绩与技术进展
  • tmux 终端复用器教程,创建一个持久的会话
  • 理解Transformer中的位置编码
  • 网络风险管理的三大关键洞察
  • 牛客 周赛110 20251007
  • Python列表初始化的陷阱:重复引用的坑
  • MongoDB
  • 实用指南:第三十三天打卡复习
  • 实用指南:Hardening fixes lead to hard questions
  • 赛前训练6 状压
  • 排序综合
  • NKOJ全TJ计划——NP11745
  • InfinityFree教程 ——免费搭建属于你的网站
  • 关于调和级数估算前n项的和
  • 10.6 模考 T4(QOJ 1836)
  • 实用指南:【Node.js 深度解析】npm install 遭遇:npm ERR! code CERT_HAS_EXPIRED 错误的终极解决方案
  • 顺序结构
  • Windows漏洞利用技巧:虚拟内存访问陷阱(2025更新)
  • Python编译期优化:隐藏在代码背后的效率魔法
  • 一篇文章带你了解 WGCLOUD运维监控系统的部署与应用
  • 选择结构
  • Python函数默认参数陷阱:可变对象的共享问题深度解析
  • 无需安装的Photoshop:网页版完整使用指南与在线图片编辑技巧
  • 求阶
  • gin 框架 - 教程
  • 赛前训练 5 树形 dp
  • 递推求解逆元
  • 一些做题记录(2025 2-3)