【题解】CF704E Iron Man

本文主要是介绍【题解】CF704E Iron Man，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

按照洛谷的题面，要么爆炸发生在一个点上，要么爆炸发生在一条边上。

先考虑爆炸发生在一个点 \(u\) 上的情况，如果将 \(u\) 提为根，那么如果有两个经过 \(u\) 的鸡贼满足经过 \(u\) 的时间相同，那么就将答案与之取 \(\min\)（假设两个鸡贼可能碰撞多次，这样肯定取到第一次）。

将内子树和外子树分开讨论，首先将路径在 LCA 处拆开，打标记后就可以启发式合并得到经过 \(u\) 的路径集合。用 set 维护这些路径，按照到达 \(u\) 的时间从小到大排序，发现不好排序。

？做法假了。

题解的做法跟上述思路截然不同。

考虑在一条链上怎么做这个问题，如果有 \(m\) 个鸡贼，将每个鸡贼看成平面图上一条线段（纵坐标为位置，横坐标为时间），然后用一条横线从下往上扫（沿时间扫），用 multiset 维护加入删除。

容易发现，当需要加入或删除某个元素的时候，只需要考虑坐标相邻的两个元素的相交情况即可。并且插入元素至 multiset 后就不需要再管元素了。

具体考虑第一次交点（也就是答案），产生答案的两个线段，在答案时间以及之前必然存在相邻的状态，否则不可能取到答案（即如果一直不是相邻的，那么中间的线段和这两个线段相交的时间不会更完）。

拓展到树只需要重链剖分即可，复杂度 \(O(m\log m\log n)\) 。

这篇关于【题解】CF704E Iron Man的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！