问题分析

我们有两个点 $A(x_A, y_A)$ 和 $B(x_B, y_B)$，它们可以构成一个合法矩形，当且仅当满足：

1. $x_A < x_B$ 且 $y_A < y_B$（$A$ 是左下角，$B$ 是右上角）。
2. 矩形内部（不包含边界）没有其他稻草人。

条件 2 等价于：在矩形 $(x_A, y_A) \to (x_B, y_B)$ 内部，不存在任何点 $C$ 满足 $x_A < x_C < x_B$ 且 $y_A < y_C < y_B$。

思路转换

我们可以固定一个点作为右上角 $B$，统计有多少个左下角 $A$ 满足条件。

对于右上角 $B$，可能的左下角 $A$ 必须满足：

• $x_A < x_B$
• $y_A < y_B$
• 在区间 $(x_A, x_B)$ 内，不存在 $y$ 坐标在 $(y_A, y_B)$ 之间的点。

关键观察

将点按 $x$ 坐标排序。考虑分治或扫描线方法。

一种有效方法是 CDQ 分治：

1. 按 $x$ 排序所有点。
2. 分治区间 $[l, r]$：
   • 递归处理 $[l, mid]$ 和 $[mid+1, r]$。
   • 统计左下角在 $[l, mid]$，右上角在 $[mid+1, r]$ 的矩形个数。

统计跨区间的矩形

对于左半部分的点（候选左下角）和右半部分的点（候选右上角）：

• 我们按 $y$ 从小到大处理右半部分的点（右上角）。
• 对于当前右点 $B$，左半部分中 $y < y_B$ 的点可能成为左下角。
• 但必须排除那些在某个“障碍点”下方的左下角。

具体来说，我们维护左半部分的点的 $y$ 坐标单调栈（递减），使得栈中点的 $y$ 是递减的，但 $x$ 递增（因为左半已按 $x$ 排序）。当我们处理一个右点 $B$ 时，在左半部分找到 $y$ 小于 $y_B$ 的点中，从高到低，第一个 $y$ 大于某个“限制”的点才会被计入。

单调栈方法

我们定义：

• 对右半部分的点按 $y$ 升序扫描。
• 对左半部分的点也按 $y$ 升序扫描（用于构建单调栈）。
• 左单调栈：栈内元素的 $y$ 严格递减。
• 当我们加入一个左点 $P$ 到栈时，弹出所有 $y < P.y$ 的栈顶元素（因为 $P$ 会挡住它们成为某些右上角的左下角）。
• 对于右点 $B$，在左栈中二分查找最后一个 $y < y_B$ 的元素，该元素到栈底的所有点都是对 $B$ 有效的左下角。

实际上更简单的做法是：

1. 左半部分按 $y$ 降序排序，右半部分按 $y$ 升序排序。
2. 对每个右点 $B$，将左半部分中 $y < y_B$ 的点加入一个数据结构（按 $x$ 排序），并保证这些点的 $y$ 是前缀最大值（单调栈思想）。
3. 在单调栈中，每个新左点会弹出栈中 $y$ 比它小的点，因此栈中 $y$ 是递减的，$x$ 递增。
4. 对于右点 $B$，在栈中二分找到第一个 $y < y_B$ 的位置，该位置到栈顶的所有点都满足：它们与 $B$ 构成的矩形内部没有其他左半部分的点（因为栈中每个点都是之前某个 $y$ 最大的点，会挡住下面的点）。

树状数组/线段树优化

另一种方法：

• 将整个点集按 $x$ 排序。
• 用树状数组维护 $y$ 坐标的前缀最大值或次大值信息，在扫描过程中快速查询对于当前右上角 $B$，有多少左点 $A$ 满足 $y_A < y_B$ 且 $(x_A, x_B)$ 之间没有 $y \in (y_A, y_B)$ 的点。
• 这等价于查询 $y$ 坐标小于 $y_B$ 的点中，$y$ 是某个区间内的最大值的那些点。

总结算法步骤

1. 按 $x$ 排序所有点。
2. CDQ 分治：
   • 递归左右区间。
   • 合并时，左半部分和右半部分分别按 $y$ 排序。
   • 对右半的每个点 $B$，将左半中 $y < y_B$ 的点加入单调栈（栈中 $y$ 递减）。
   • 栈的大小即为对应当前 $B$ 的合法左下角数量（因为栈中每个点与 $B$ 之间在左半部分没有其他点阻挡）。
3. 累加所有分治层的答案。

时间复杂度

• 排序：$O(N \log N)$
• CDQ 分治 + 单调栈：$O(N \log N)$
• 总复杂度：$O(N \log N)$，可处理 $2\times 10^5$ 的数据规模。

这样，我们就能高效地统计所有满足条件的矩形数目。