P13889 [蓝桥杯 2023 省 Python A] 子矩阵
洛谷原题，链接：https://www.luogu.com.cn/problem/P13889
思路：
核心问题
给定 n 个二维点 (x, y) 和一个整数 d，要求找到一个点的子集，满足子集中 y 的最大值 - y 的最小值 ≥ d，且该子集的x 的最大值 - x 的最小值尽可能小，输出这个最小的 x 差值；若不存在满足条件的子集，输出-1。
核心算法框架
排序 + 滑动窗口（双指针） + 两个单调队列，是解决这类带最值约束的区间最小差值问题的经典最优解法，整体时间复杂度O(nlogn)（排序主导），适配n≤105的大数据规模（代码中N=100010）。
1. 基础工具：快速读入函数read
手写getchar版快速输入，比cin/cout快数倍，避免大数据量下的输入超时；
支持处理负数（本题中 x/y 应为正，不影响）。
2.变量与结构体定义
p1：维护窗口内 y 的最大值的单调递减队列（队头是 y 最大的点的下标）；
p2：维护窗口内 y 的最小值的单调递增队列（队头是 y 最小的点的下标）。
3. 预处理：按 x 升序排序
核心关键步骤：排序后，任意区间[le, r]的 x 差值为a[r].x - a[le].x，且x 差值随 r 增大而增大、随 le 增大而减小，为后续滑动窗口（双指针） 提供单调性基础，保证能找到最小 x 差值。
4. 初始化
5.核心：滑动窗口 + 单调队列维护（外层遍历左边界 le）
这是代码的核心，分3个关键动作，所有操作均为线性 O (n)，无嵌套冗余
动作 1：清理队列的过期队头
队列中存的是点的下标，若下标<le，说明该点已在当前窗口[le, r]外，直接弹出队头，保证队列中仅保留窗口内的点。
动作 2：扩展右边界 r，直到满足约束
当当前窗口内的y最大值 - y最小值 < d（不满足条件），且 r 未遍历完所有点时，将 r 右移并加入两个单调队列，单调队列的维护规则：
最大队列 p1（单调递减）：新点 r 的 y 比队尾大时，队尾的点永远不可能成为后续窗口的 y 最大值，直接弹出；直到队尾 y≥a [r].y，再将 r 加入队尾，保证队头始终是窗口内 y 最大的点。
最小队列 p2（单调递增）：新点 r 的 y 比队尾小时，队尾的点永远不可能成为后续窗口的 y 最小值，直接弹出；直到队尾 y≤a [r].y，再将 r 加入队尾，保证队头始终是窗口内 y 最小的点。
动作 3：更新最小 x 差值当停止扩展 r 时，若 r≠n（说明找到满足条件的窗口），此时窗口[le, r]的 x 差值为a[r].x - a[le].x，用该值更新全局最小 ans。
6. 结果输出
若 ans 仍为初始的无穷大，说明遍历完所有窗口都未找到满足y最大-y最小≥d的子集，输出-1；
否则输出最小的 x 差值 ans。
关键细节与算法优势
1. 单调队列的核心作用
避免对每个窗口重新遍历求 y 的最大 / 最小值（暴力法O(n2)），通过O (1) 获取窗口最值，将滑动窗口的时间复杂度从O(n2)降至O(n)。
2. 双指针的单调性
因为点按 x 升序排序，左边界 le 右移时，右边界 r 不会左移，le 和 r 各仅遍历 n 次，保证线性复杂度。
3.** 下标统一**
代码中点的下标是 1~n，双指针 le/r 是 0~n，队列存储的是点的 1 维下标，边界判断清晰，无越界风险。
4. 时间复杂度
排序：O(n log n)（主导复杂度）；
滑动窗口 + 单调队列：O(n)（每个点入队 / 出队各一次）；
整体：O(n log n)，完美适配n≤105的评测用例。
7.总结
将二维约束问题（x 最小差 + y 最值差≥d）通过按 x 排序转化为一维滑动窗口问题，再用两个单调队列分别维护窗口内 y 的最大 / 最小值，最终在最优时间内找到答案
最终代码：
完结撒花
团队招人：https://www.acgo.cn/application/1811737919264829440
