Luogu4632 [APIO2018] New Home 新家

有 \(n\) 个商店，第 \(i\) 个商店在位置 \(x\) ，类型是 \(t\) ，在 \(a\) 年开业，\(b\) 年关闭。\(m\) 次询问，每次询问若 \(l\) 年住在位置 \(y\) ，不便利度是多少。不便利度定义为 \(\max \{到类型\;t\;的最近的商店的距离\}\)。
\(n, m \le 3\times 10^5\)。

　　数据结构 线段树 二分 扫描线

　　有几个细节比较恶心，初看可能有点头晕，但是想清楚了实现就 easy 多了。

　　根据时间进行扫描线，然后考虑对于每个询问进行 \(\tt check\)，因为这个最近距离有点难搞，于是可以考虑二分，同时我们记一个 \(pre_i\) 表示和 左边和 \(i\) 点同色的最后一个点，然后一个 \(mid\) 合法当且仅当 \(\min_{i = y + mid}^{\infty}\{pre_i\} \ge y - mid\)（其中 \(y\) 表示询问位置）。

　　使用 set 可以方便地维护 \(\{pre_i\}\)，然后可以使用线段树维护 \(\min\) 值，可以在线段树上面二分做到 \(\mathcal O(n\log n)\)。

　　然后有几个细节：

• 因为商店的坐标可能相同，于是离散化不能去重，要将一些坐标相同商店映射到不同的标号。
• 线段树二分到 \(p\) 后，只是求到了右边的点作为最远不便利的点的情况，还要和左边的情况取 \(\max\)。
• 如果没有前驱，\(pre_i\) 设为 \(-\infty\)。
• 在 \(\infty\) 处建立一个超级点，其 \(pre\) 为所有类型商店的最后出现位置。

　　然后就没啥了，代码。