U371414 网格 题解

Elup · 2024-07-26 19:20:06 · 题解

传送门

首先简化问题：把同向且相交的线段合并，这样之后竖直线段之间就只能通过水平线段连通了。

考虑用扫描线从下向上扫，实时维护一个区间集合，区间 [l,r] 表示所有横坐标在 [l,r] 内并处于扫描线上的竖直线段互相连通，这样的区间显然互不相交。

考虑在扫描并维护区间集合的过程中把连通线段加入并查集以支持查询，

设竖直线段横坐标为 x ，水平线段横坐标为 [x_l,x_r] ，具体过程如下：

• 竖直线段第一次处于扫描线上时，向区间集合中加入区间 [x,x] 。如果有区间 [l,r] 包含 x ，则设 x_0,x_1 分别为 x 左边与右边的首条竖直线段，将 [l,r] 分裂为 [l,x_0] 与 [x_1,r] 。

• 竖直线段刚好被扫描线超过时，将其与包含 x 的区间中的任意一条其他线段在并查集中合并。如果 x 刚好是一个区间的 l/r ，则重新维护区间的 l/r ，类似加入时的分裂。

• 水平线段第一次处于扫描线上时，把所有与 [x_l,x_r] 有交的区间在区间集合中暴力合并。

时间复杂度能得到保证的大致证明：考虑每条竖直线段，将扫到它时视作入栈，将水平线段把它合并时视作出栈，则一条竖直线段最多只会进出栈一次（被合并后不会再在暴力合并时被枚举到）。

查询时二分查找一个点在哪条线段上即可。

注意特判两个点是同一个点但不在任何线段上的情况。