题解：地毯覆盖查询（反向遍历优化）

一、解题核心思路

本题的关键是找到覆盖目标点 (x,y) 的 最上面的地毯（即编号最大的地毯）。由于地毯按编号从小到大铺设，后铺的地毯会覆盖先铺的，因此无需遍历所有地毯，只需 从最后一张地毯（编号最大）向前遍历，找到第一个覆盖目标点的地毯即可，效率更高。

二、关键逻辑推导

1. 地毯覆盖判断： 地毯的左下角坐标为 (a,b)，x轴长度为 g，y轴长度为 k，则地毯覆盖的区域满足：

   • x 范围：a ≤ x ≤ a + g（左边界 ≤ 目标x ≤ 右边界）
   • y 范围：b ≤ y ≤ b + k（下边界 ≤ 目标y ≤ 上边界） （边界包含在内，符合题目要求）

2. 反向遍历优化： 由于后铺的地毯覆盖先铺的，编号越大的地毯越靠上。因此从编号 n 遍历到 1，一旦找到覆盖目标点的地毯，直接返回其编号，无需继续遍历，时间复杂度最优为 O(1)（目标点被最后一张地毯覆盖），最坏为 O(n)（目标点被第一张或未被覆盖），完全适配 n≤1e4 的数据范围。

三、具体解题步骤

1. 输入读取：
   • 读取地毯数量 n；
   • 存储每张地毯的信息（a,b,g,k），可使用数组或结构体，索引从 1 到 n（对应地毯编号）；
   • 读取目标点坐标 (x,y)。
2. 反向遍历判断：
   • 从 i = n downto 1：
     • 计算当前地毯的右边界 a + g 和上边界 b + k；
     • 判断 x 是否在 [a, a+g] 且 y 是否在 [b, b+k]；
     • 若满足，输出 i 并结束程序。
3. 无覆盖处理：
   • 遍历结束后未找到覆盖的地毯，输出 -1。

四、完整代码实现

#include <iostream>
#include <vector>
using namespace std;

struct Carpet {
    int a, b, g, k;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Carpet> carpets(n + 1); // 1-based 索引，对应地毯编号
    for (int i = 1; i <= n; ++i) {
        cin >> carpets[i].a >> carpets[i].b >> carpets[i].g >> carpets[i].k;
    }

    int x, y;
    cin >> x >> y;

    // 反向遍历，找第一个覆盖目标点的地毯
    for (int i = n; i >= 1; --i) {
        int a = carpets[i].a;
        int b = carpets[i].b;
        int right = a + carpets[i].g;
        int top = b + carpets[i].k;
        if (x >= a && x <= right && y >= b && y <= top) {
            cout << i << endl;
            return 0;
        }
    }

    // 未被任何地毯覆盖
    cout << -1 << endl;
    return 0;
}

五、代码解释

1. 数据存储：使用 vector<Carpet> 存储地毯信息，1-based 索引与地毯编号一致，方便遍历。
2. 覆盖判断：直接计算地毯的右边界和上边界，通过简单的区间判断即可确定是否覆盖目标点，无需复杂几何计算。
3. 效率优化：反向遍历确保找到的第一个覆盖地毯就是最上面的，避免无效遍历，代码简洁高效，无冗余操作。

六、复杂度分析

• 时间复杂度：O(n)。最坏情况下遍历所有地毯，n≤1e4 时操作数极少，运行速度快。
• 空间复杂度：O(n)。存储 n 张地毯的信息，空间开销可控（每张地毯4个整数，n=1e4 时仅需约 160KB）。

该代码逻辑清晰，效率最优，完全适配题目要求，能快速处理所有测试用例。