题解：KRALJEVI（COI 2010 T1）

题目分析

题目要求统计矩形四条边上的橡树数量（矩形四边平行于坐标轴，边上的橡树需被砍掉，内部和外部不计算），其中橡树数量 $N$ 和查询次数 $P$ 均可达 $3 \times 10^5$，因此需要高效的查询方法，暴力枚举会超时。

矩形的四条边特征：

• 左边界：$x=X_1$，$y \in (Y_1, Y_2)$（排除顶点，避免重复统计）
• 右边界：$x=X_2$，$y \in [Y_1, Y_2]$（包含顶点）
• 下边界：$y=Y_1$，$x \in [X_1, X_2]$（包含顶点）
• 上边界：$y=Y_2$，$x \in (X_1, X_2)$（排除顶点）

核心目标是快速统计每条边上的点数量，且避免顶点重复计数。

解题思路

1. 预处理排序

将所有橡树的坐标存储为两种形式并排序：

• $px$ 数组：元素为 $(x, y)$，按 $x$ 升序、$x$ 相同时按 $y$ 升序排序，用于快速查询固定 $x$ 对应的 $y$ 区间点；
• $py$ 数组：元素为 $(y, x)$，按 $y$ 升序、$y$ 相同时按 $x$ 升序排序，用于快速查询固定 $y$ 对应的 $x$ 区间点。

2. 二分统计点数

利用 upper_bound 和 lower_bound 的特性（前者返回第一个大于目标值的迭代器，后者返回第一个大于等于目标值的迭代器），精准统计各边的点数量：

• 左边界：$px$ 中 $x=X_1$ 且 $y \in (Y_1, Y_2)$ 的点数量 = upper_bound(px, (X1,Y2)) - upper_bound(px, (X1,Y1))；
• 上边界：$py$ 中 $y=Y_2$ 且 $x \in (X1,X2)$ 的点数量 = upper_bound(py, (Y2,X2)) - upper_bound(py, (Y2,X1))；
• 右边界：$px$ 中 $x=X2$ 且 $y \in [Y1,Y2]$ 的点数量 = lower_bound(px, (X2,Y2)) - lower_bound(px, (X2,Y1))；
• 下边界：$py$ 中 $y=Y1$ 且 $x \in [X1,X2]$ 的点数量 = lower_bound(py, (Y1,X2)) - lower_bound(py, (Y1,X1))。

3. 结果计算

将四条边的统计结果相加，即为单次查询的答案。

算法细节

• 快速读入：使用 fread 实现快速输入，适配 $3 \times 10^5$ 级别的数据量，避免输入超时；
• 二分正确性：排序后的数组保证了二分查找的单调性，upper_bound 和 lower_bound 的组合使用精准区分了“开区间”和“闭区间”的统计需求；
• 去重逻辑：通过区分边的端点包含性，避免了矩形四个顶点被重复计数。

复杂度分析

• 预处理阶段：排序 $px$ 和 $py$ 的时间复杂度为 $O(N \log N)$；
• 查询阶段：单次查询包含 4 次二分操作，每次二分的时间复杂度为 $O(\log N)$，$P$ 次查询的总时间复杂度为 $O(P \log N)$；
• 总时间复杂度：$O(N \log N + P \log N)$，可高效处理题目中的数据范围。

总结

本题的核心是排序 + 二分查找的组合应用，通过预处理将点按不同维度排序，利用二分快速统计区间内的点数量，同时通过端点包含性的区分避免重复计数。这种思路是处理大规模数据区间查询问题的经典方法，既保证了时间效率，又能精准满足题目需求。对于类似的“平面点集区间查询”问题，排序 + 二分是首选的高效解决方案。