P4125 [WC2012]记忆中的水杉树
给定 \(n\) 个平面上 不相交 的线段，规定将线段按照水平竖直的 \(4\) 个方向移动至无穷远，若没有碰到任何其他线段则为合法。要求完成 \(2\) 个问题：
给定移动排列和方向，询问当前移动中首次非法操作的位置。
要求给定一组合法的移动排列和方向。
\(n\leq10^5,|a_i|\leq10^9\) 。
首先有一个暴力的做法：将 \(n\) 条边之间的先后顺序（即拓扑序）建出边来。然而这样的做法是 \(O(n^2)\) 的，不能接受。然而这种建边的拓扑序的方式是可行的。对于操作 \(2\) ，由于线段一定可以从某一方向依次移动并保证合法，所以只用输出拓扑序。而对于操作 \(1\) 则可以用 \(2\) 棵线段树维护后 \(i\) 个点在纵向和横向的拓扑序最小值最大值，每次只需要查询对应离散化区间内的最值是否小于/大于自己的拓扑序即可。
问题来到了如何建边。注意到有很多边是重复的，没有必要，比如下图中会建出 \(EF\rightarrow AB,CD\rightarrow AB,EF\rightarrow CD\) 三条边，而事实上为了得出字典序需要的边是 \(2\) 条。若是有一种方法能使得每条边只和其正上方和正下方的边连边就好了。那么这个方法就是扫描线。
考虑在每条边进数据结构之前先查找出“小于”它和“大于”它的首条线段并连边，这样的边数就是 \(2n\) 级别的。带插入修改查前驱后继当然使用 set ，然而问题在于如何比较两条线段的大小（甚至是动态比较）。
由于题目保证线段不相交，所以所有线段都有插入时谁大谁在删除前就一定还是大的，所以可以动态比较 \(2\) 点在插入时的点在线段上的大小即可。整体复杂度是连边的 \(O(n\log n)\) ，拓扑排序的 \(O(n)\) 和线段树维护最值的 \(O(n\log n)\) 。整体复杂度为 \(O(n\log n)\) 。
标签：连边,log,杉树,线段,WC2012,rightarrow,拓扑,P4125 From： https://www.cnblogs.com/zhouzizhe/p/16909383.html