【1】做题心得 - 杂题 - 矩形【扫描线】【线段树】【数据结构】

· · 题解

问题描述

因为对菠萝（polo）忍无可忍，景景（dzd）使用圣剑在地上划出了许多纵横交错的沟壑来泄愤。这些沟壑都严格与 x 轴平行或垂直。

菠萝嘲笑了景景无聊的行为，然后做了一件更加无聊的事。他蹲下来数这些沟壑的条数。

数着数着，菠萝意识到一个问题，那就是因为圣剑的威力太大，划出的沟壑太多，地面就会塌陷。而如果两条水平的沟壑和两条垂直的沟壑相交组成了一个矩形，那么塌陷的危险就会进一步增加。

现在菠萝已经数了 n 条沟壑，他想知道这些沟壑组成了多少个矩形。

题解

我们考虑枚举每一条竖线，对应着先处理相交的横线。

然后我们枚举另一个竖线，注意到从左往右扫符合条件的横线是单调减少的，考虑优先队列去减少。

然后直接树状数组维护剩余横线，查询即可。