企业官网建设流程全解析

不少打算法竞赛的朋友第一次见到 P1003 铺地毯这道题，第一反应都是“这不就是个二维数组模拟吗”，然后开开心心写了个int a[10005][10005]，一运行直接内存爆炸。还有人想用扫描线、差分数组硬刚，结果发现这题根本用不上。说实话，这道题能进 NOIP 提高组，靠的不是算法难度，而是它考察了一个非常容易被忽略的思维习惯——反着读题。这篇博文我会从题目本质、正序模拟的坑、倒序判断的完整思路、多语言代码实现、边界踩坑点，以及这类“最后覆盖者”问题的通用解法几个方面，一次性给你讲透。无论你是刚开始刷洛谷的初学者，还是准备冲刺更高组别的选手，这篇内容都值得认真看完。

1. 题目到底在说什么：一道披着“模拟”外衣的思维题

先回顾一下题目描述。地面上从下往上依次铺了 n 张地毯，编号从 1 到 n。每张地毯给出左下角坐标 (x, y) 以及沿 x 轴和 y 轴方向的长度 a、b，那么它的右上角坐标自然就是 (x + a, y + b)。然后给出一个查询点 (x0, y0)，要求判断覆盖这个点的最上面一张地毯是哪张，如果没有任何地毯覆盖就输出 -1。

这题的 n 最大可以到 10000，坐标范围是 0 到 100000。看到这个数据范围，很多人的第一反应是：那我开一个二维数组，把每张地毯的格子都填上编号，最后直接读查询点不就行了？这就是典型的“看到题目就想模拟”的思维定式。但仔细算一笔账：如果地毯面积为 10^10 量级，你开一个 100000 × 100000 的 int 数组，占用内存大约是 40000000000 字节，也就是 40GB。这在竞赛环境下是完全不可能的，普通电脑也扛不住。

所以这题考的不是你模拟得有多快，而是你能不能跳出“铺地毯”这个具象操作，直接从几何关系出发判断点与矩形的位置关系。每一张地毯本质就是一个轴对齐矩形，查询点落在矩形内部的条件非常直接：x <= x0 <= x + a且y <= y0 <= y + b。有了这个认知，整道题的性质就变了——它不是模拟题，而是一道静态几何查询题，考察的是最基础的区间判断能力。

很多人拿到这道题会去翻题解，然后发现代码极短，只有十来行，于是觉得这题“水”。但真正值得思考的地方恰恰在这里：为什么这么短的代码能通过 10000 的数据范围？因为判断一个点是否在矩形内是 O(1) 的操作，遍历 n 张地毯也只需要 O(n) 的时间，整体复杂度 O(n)，10000 的数据量在一秒内轻松跑完。内存上，我们只需要存 n 组 x、y、a、b 四个整数，开四个一维数组甚至一个结构体数组就够了，空间 O(n)，完全没问题。

从题目设计者的角度想一想，这道题其实是在提醒选手：不一定所有几何题都要把图形画出来或者填进数组里。点与矩形的位置关系，通过数学条件判断是最高效、最节省资源的方式。后面很多计算几何题目，比如判断点在多边形内、判断线段相交，本质上也都是先做数学化的转化，再做逻辑判断。这道题就是那个“启蒙课”。

2. 第一直觉为什么容易翻车：正序模拟的局限与性能陷阱

我最初做这道题的时候，和绝大多数人一样，第一反应就是正序模拟：把地毯按编号从 1 到 n 依次“铺”到一张巨大的画布上，后铺的覆盖先铺的，最后查看查询点上的编号。这个思路本身没有错，错在实现方式上。

如果你用二维数组模拟，假设坐标上限是 100000，那么数组至少要开到 100001 × 100001 才能覆盖所有可能的点。这个大小在 C++ 里是定义不出来的，即使你开全局数组也会直接编译失败或者运行时崩溃。有些朋友会说：“那我只开到覆盖到所有地毯的最大范围不就行了？”问题是每张地毯的范围不同，最坏情况下就是覆盖整个坐标空间，你还是得开一个近乎 10^10 的数组。

即使退一步说，某道题的坐标范围缩小到 1000，用二维数组模拟可以跑通，但仔细想想，你的时间复杂度是多少？每张地毯的填充需要遍历 a × b 个格子，如果 a 和 b 都是 1000，那么铺一张地毯就是 10^6 次操作，n 张地毯就是 n × 10^6 次操作。当 n 也是 1000 时，总操作数是 10^9，在一秒的限制下大概率超时。更别说坐标系更大或者 n 更大的情况了。

所以正序模拟在思路上是“最老实”的，但在工程上往往是最差的方案。它的核心问题在于：我们把问题过度具象化了。地毯是一个矩形，但矩形不一定非要用格子填满来表示，它可以用一组坐标参数来精确描述。你只需要记住这一组参数，然后通过数学条件判断某个点是否在其中，这样既不需要填充开销，也不需要消耗大块内存。

我在学习数据结构的时候，一位前辈跟我说过一句话，我至今印象深刻：“能用公式描述的，就不要用枚举；能用参数表达的，就不要用数组。”P1003 正是这句话的绝佳例证。查询点落在矩形内，本质上就是一个公式问题：x <= x0 && x0 <= x + a && y <= y0 && y0 <= y + b。你把它变成公式，整个问题的复杂度就从“铺地毯”降到了“查参数”。

另一个容易翻车的点是正序思维对“最上面”这个概念的处理。正序模拟后，查询点上最终的编号一定是最上面那张地毯的编号，因为后铺的覆盖了先铺的，这没问题。但如果你的思维停留在“铺”的动作上，你会不由自主地想去做覆盖操作和高维存储。而倒过来想，一个点被哪张地毯覆盖，你应该从最上面的地毯开始往下找，找到第一张覆盖它的，就是答案。这个思路不需要任何覆盖操作，只需要从 n 到 1 遍历，找到第一个满足矩形包含条件的编号，直接输出并退出循环。如果全部遍历完都没有，输出 -1。

从工程角度看，这个倒序思维还有一个隐藏优势：它可以“提前返回”。正序模拟必须等所有地毯都铺完才能查询，而倒序判断只要找到一张覆盖查询点的地毯就能立刻退出，平均情况下执行的判断次数远少于 n。当然，最坏情况（点在最底层地毯上，或者无覆盖）还是要遍历全部 n 张，但即便如此，O(n) 也是完全可以接受的。

3. 倒序判断思路拆解：从“谁铺在上面”到“谁最先被问到”

倒序判断的核心逻辑，其实是用一个生活直觉去替换一个工程模拟。想象你在收拾一堆叠起来的毯子，想知道最底下压着的那张毯子是什么颜色。你不会把上面的毯子一张一张搬开去数，而是会直接从最上面开始看，如果最上面这张不是你要找的，再掀开它看下面那张，直到找到为止。这里最关键的一点是：你只关心“查询点”这一个位置，整张地毯其他部分的状态你不关心、不需要知道、也不应该花时间去维护。

映射到代码上，就是用一个 for 循环从 n 遍历到 1。对每一张地毯 i，取出它的 (x[i], y[i], a[i], b[i])，计算右上角坐标 (x[i] + a[i], y[i] + b[i])，然后判断查询点 (x0, y0) 是否满足：

x[i] <= x0 <= x[i] + a[i] y[i] <= y0 <= y[i] + b[i]

如果满足，输出 i 并结束程序；如果循环结束都没有找到，输出 -1。

很多初学者会问：“为什么从 n 往 1 找，而不是从 1 往 n 找？”因为编号越大代表地毯铺得越靠上。题目说了“从下往上依次铺”，也就是说编号 1 在最底下，编号 n 在最顶上。查询点如果被多张地毯覆盖，那么编号最大的那张就是最上面那张。我们从 n 开始往下找，第一次遇到符合条件的，就一定是覆盖查询点的最上面那张地毯。如果从 1 往上找，你找到的是最底层的那张，还得继续往后遍历，直到找完所有覆盖这个点的地毯，才能比较出编号最大的，这样虽然也能得到正确答案，但你必须完整遍历 n 张地毯且无法提前退出，效率差得多。

这个过程里不需要数组模拟，不需要标记覆盖，不需要处理“铺上去又盖住”的关系，一切都靠坐标计算完成。代码结构也非常简单，C++ 里十几行就能搞定。包含头文件、定义数组、读入数据、倒序判断、输出结果，一气呵成。

为了让你更直观地理解这个判断过程，我给一个具体的例子。

假设有三张地毯：

• 地毯 1：左下角 (1, 1)，长度 2，宽度 2，覆盖区域 [1,3] × [1,3]
• 地毯 2：左下角 (2, 2)，长度 2，宽度 2，覆盖区域 [2,4] × [2,4]
• 地毯 3：左下角 (3, 3)，长度 1，宽度 1，覆盖区域 [3,4] × [3,4]

查询点为 (3, 3)。倒序判断：

• 先看地毯 3：x=3, y=3, a=1, b=1，覆盖 x 范围 [3,4]，y 范围 [3,4]。(3,3) 满足，输出 3。程序结束。

如果查询点是 (2, 2)：

• 看地毯 3：x 范围 [3,4]，(2,2) 不在其中，跳过。
• 看地毯 2：x 范围 [2,4]，y 范围 [2,4]，(2,2) 满足，输出 2。

如果查询点是 (1, 1)：

• 看地毯 3，不满足；看地毯 2，x 范围 [2,4]，(1,1) 不在其中，跳过；看地毯 1，x 范围 [1,3]，y 范围 [1,3]，满足，输出 1。

如果查询点是 (0, 0)：

• 遍历完三张地毯都不满足，输出 -1。

从这个例子你可以看到，算法的每一步都是纯粹的数值比较，没有任何数据结构上的花样，但正确性有非常清晰的数学保证。

4. 参考实现与运行效率对比：C++、Python、Java 怎么选

我分别用三种语言写了一份参考实现，方便不同技术栈的朋友对照学习。核心逻辑完全一致，区别主要在输入输出和数组定义方式上。

C++ 版本是竞赛中最常见的写法，利用scanf快速读入，数组直接开在全局区，避免栈溢出：

#include <cstdio> const int MAXN = 10005; int x[MAXN], y[MAXN], a[MAXN], b[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d%d%d", &x[i], &y[i], &a[i], &b[i]); } int x0, y0; scanf("%d%d", &x0, &y0); for (int i = n; i >= 1; i--) { if (x0 >= x[i] && x0 <= x[i] + a[i] && y0 >= y[i] && y0 <= y[i] + b[i]) { printf("%d\n", i); return 0; } } printf("-1\n"); return 0; }

Python 版本用列表存数据，sys.stdin.read()一次性读入提升效率。如果你用input()逐行读，在 n=10000 时也能过，但如果往后做更复杂的题目，建议养成批量读入的习惯：

import sys def main(): data = list(map(int, sys.stdin.read().split())) n = data[0] idx = 1 carpets = [] for _ in range(n): x, y, a, b = data[idx], data[idx+1], data[idx+2], data[idx+3] idx += 4 carpets.append((x, y, a, b)) x0, y0 = data[idx], data[idx+1] for i in range(n-1, -1, -1): x, y, a, b = carpets[i] if x <= x0 <= x + a and y <= y0 <= y + b: print(i + 1) return print(-1) if __name__ == "__main__": main()

Java 版本用BufferedReader或Scanner都可以，但由于数据量不大，Scanner也能接受。为了稳妥，我用BufferedReader：

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int[] x = new int[n + 1]; int[] y = new int[n + 1]; int[] a = new int[n + 1]; int[] b = new int[n + 1]; for (int i = 1; i <= n; i++) { st = new StringTokenizer(br.readLine()); x[i] = Integer.parseInt(st.nextToken()); y[i] = Integer.parseInt(st.nextToken()); a[i] = Integer.parseInt(st.nextToken()); b[i] = Integer.parseInt(st.nextToken()); } st = new StringTokenizer(br.readLine()); int x0 = Integer.parseInt(st.nextToken()); int y0 = Integer.parseInt(st.nextToken()); for (int i = n; i >= 1; i--) { if (x[i] <= x0 && x0 <= x[i] + a[i] && y[i] <= y0 && y0 <= y[i] + b[i]) { System.out.println(i); return; } } System.out.println(-1); } }

三种语言的时间复杂度完全一致，都是 O(n)，空间复杂度也都是 O(n)。实际跑下来，C++ 最快，几乎在几毫秒内完成；Java 稍慢但在本题的数据范围内毫无压力；Python 虽然是最慢的，但 10000 次循环也只是一眨眼的事。对于这道题，任何语言都不会有性能瓶颈，关键还是思路对不对。

有一个实现细节值得单独说：边界条件。判断条件里用的是<=而不是<。很多朋友在写这类区间判断时容易把端点丢掉，导致恰好落在边界上的点被判定为无覆盖，输出 -1，最后怎么调试都找不到原因。地毯的覆盖范围是闭区间，左下角 (x, y)，右上角 (x+a, y+b)，四个边界点都是属于地毯的。这一点题目描述里虽然没有反复强调，但从“覆盖”一词的常识就能推断出来。如果你把条件写成x0 > x && x0 < x + a，那么边界上的点全部会漏判。

5. 踩坑实录：边界条件、坐标计算顺序与变量命名

我一开始做这道题时，犯过一个现在想起来觉得很可笑的错误：我把右上角坐标存下来了，但没有直接用x + a而是先计算了一次a = x[i] + a[i]，把原来的长度覆盖掉了。因为数组 a 既用来存“长度”又用来存“右上角”，后遍历时再想用长度就全乱了。这个问题在代码短的时候很容易被忽略，但一旦养成乱复用变量的习惯，后面写复杂题时会相当痛苦。

更隐蔽的一个坑是：输入数据给的 a 和 b 是长度，不是右上角坐标。题目描述很明确，左下角 (x, y)，长度 a、b，所以右上角是 (x+a, y+b)。但有些人会误以为给的是右上角坐标，直接拿 x 和 a 当成一个区间的两个端点去判断。这种错误在有样例数据的时候能很快发现，因为样例的输出会不对。但如果自己脑内验算，很容易因为惯性思维而错过。

还有一个关于边界判断顺序的建议。判断条件里我习惯写成：

x[i] <= x0 && x0 <= x[i] + a[i] && y[i] <= y0 && y0 <= y[i] + b[i]

从左到右依次判断 x 方向下界、x 方向上界、y 方向下界、y 方向上界。这个顺序无关紧要，因为&&是短路运算，一旦某个条件不满足，后续条件就不会执行。但从可读性角度，按坐标轴的顺序来写最自然。有些人喜欢先判断 y 再判断 x，也没问题，只是个人习惯。

变量命名方面，我在 C++ 版本里直接用了x, y, a, b四个数组，因为题面的变量名就是这些，对应关系一目了然。但如果你想把代码写得更通用，可以改成xLeft, yBottom, xLength, yLength之类更长的名字。竞赛里为了敲代码速度通常用短名，但初学阶段建议用能看懂的命名，否则一周之后你自己都忘了a[i]到底存的是长度还是右上角坐标。

还有一个小陷阱是输出格式。题目要求输出一个整数，换行结尾。有些同学会在输出末尾多加空格或者漏掉换行，虽然判题系统通常不敏感，但严格意义上还是应该按标准格式来。C++ 用printf("%d\n", i)或者cout << i << endl都没问题；Python 用print(i)默认换行，正好。

从“踩坑”的角度说，这题真正的难点不在算法，而在细心。坐标范围大、数据量中等、逻辑简单，出错的概率主要来自三个地方：数组越界、边界条件写错、变量复用导致逻辑混乱。如果你在调试时发现答案总是差 1 或者输出 -1 和正确答案交替出现，优先检查这三类问题。

6. 从题目内到题目外：一类“最后覆盖者”问题的通用解法

做完 P1003，如果你只是记下“倒着遍历”这个技巧，那收获就太少了。这道题背后其实是一整类问题：在若干次区间覆盖或矩形覆盖之后，查询某个点的最终状态或者覆盖它的最后一次操作是谁。这类问题在竞赛和实际工程中都非常常见，比如给画布多次填充颜色后问某个像素点的颜色，比如组装零件时多个图层叠加后问某个坐标属于哪个图层。

解决这类“最后覆盖者”问题的通用策略是：从最后一次覆盖操作开始，向前依次检查目标点是否在本次覆盖范围内。第一次找到的满足条件的操作，就是最后覆盖者。这个策略的数学基础是覆盖关系的传递性——如果一次操作覆盖了目标点，且它是从后往前遇到的第一个覆盖者，那么更早的操作即使也覆盖目标点，也会被它压在底下，不影响最终状态。

把这个思想抽象成模型，你会得到一张覆盖面非常广的“题目地图”：

• 一维版本的 P1003：多次给区间染色，查询某个点最后一次被哪次操作覆盖。典型题如洛谷 P1047 校门外的树（虽然那题是去除区间，但思路相似）。
• 二维版本的 P1003：就是本题，矩形覆盖后查询点。
• 三维推广：多个长方体堆叠，查询点被哪个长方体覆盖，判断条件多一个 z 维度。
• 时间维度推广：操作按时间顺序发生，查询某个时刻某个位置的状态。

在这些所有版本中，只要操作次数是有限的、覆盖关系是静态的、查询次数少，倒序判断都是首选方案。因为倒序判断天然利用“覆盖”的反对称性：后发生的覆盖在逻辑上优先于先发生的覆盖。

如果查询次数很多，比如有 m 次查询，每次查一个不同点，倒序遍历一次就是 O(nm)，在 n 和 m 都很大时可能超时。这时候你就需要更高级的技巧了：把操作离线下来，按覆盖的优先级（比如时间戳）排序，然后用线段树、扫描线或者差分数组做批量处理。P1003 目前的 n 和数据范围不需要这些，但当你做更难的题目时，这个升级路径是清晰存在的。

当年我做这道题时的体会是：它能进入提高组，不是因为算法难度，而是因为它对“思维惯性”的考察。很多人会条件反射地去模拟过程，而忽略了一个事实——模拟只是为了得到结果，如果数学判断能直接得到结果，模拟就是多余的。这一点放在工程里也非常重要：你的代码越贴近问题的本质，就越不容易受到数据规模变化的冲击。

7. 进一步扩展：如果 n 更大、查询更多该怎么办

就像前面提到的，P1003 的原版数据范围并不大。但如果你觉得这个题目太简单，想挑战一下自己的数据结构能力，可以自己把题目改造一下，比如把 n 提升到 10^5，把查询次数提升到 10^5，然后思考怎么批量处理。

首先是“多次查询”的版本。对于每个查询点，倒序遍历所有地毯是 O(nm)，在 n=m=10^5 时显然是 10^10 量级，不可接受。这时候，你得把地毯按照“从上层到下层的顺序”做一些预处理。但这里有个问题：地毯的覆盖关系是任意的，两个矩形可能部分重叠、完全包含或者不相交，并不存在天然的树形层次关系，所以不能简单地用区间树排序。

一个可行思路是扫描线。把所有地毯的上下边界按 y 坐标排序，然后沿 y 轴方向扫描。扫到一张地毯的下边界时，把它的 x 区间插入到一个有序结构里；扫到上边界时移除。查询点出现在某一时刻，你需要知道当前“激活”的 x 区间里，哪个地毯的编号最大。这个“最大编号”查询可以用区间最大值线段树实现，插入和删除的复杂度都是 O(log n)，每次查询也是 O(log n)，整体复杂度 O((n+m) log n)。但这个实现远比本题复杂，而且要考虑y坐标相同的边界处理顺序。

如果你只是想把原题数据改大一点，用“倒序判断”依然可行，因为它的 O(n) 在 n=10^5 时没有任何问题。只有当查询次数也变大时，你才被迫去优化。这其实是一个很好的训练路径：先用最简单的方法 AC 一道题，然后想一想数据范围在哪些维度上扩大时，你的算法会失效，再针对性地学习更高级的数据结构来突破瓶颈。

另外补充一个细节：扫描线处理矩形覆盖时，“激活区间”的管理通常用平衡树或者线段树，如果你用 C++，最方便的是std::set维护当前激活地毯编号的有序列表，查找某个 x 坐标被哪些地毯覆盖时，需要额外的区间结构。其实更常见的做法是把 x 坐标离散化后用线段树节点存“当前最大覆盖编号”。这些内容属于更进阶的范畴，如果你暂时用不到，可以先收藏，等做到相关题目再回来消化。

8. 我对这道题的三点额外体会

第一，刷题不要只看 AC 率。P1003 的通过率高，不代表它不值得仔细研究。恰恰因为通过率高，题解区里的做法更丰富，你可以看到各种风格的代码，有结构体版的、有四个数组版的、有用 pair 的、有只存右上角坐标的。每一种写法背后都是不同的编程习惯和思维模式，多读几篇题解，相当于快速看了几位选手的脑内过程，收获远比一遍 AC 大。

第二，边界条件永远值得单独写测试。我在写这道题的代码时，会自己构造几个小样例，包括查询点恰好在左下角端点、恰好在右上角端点、恰好在地毯边缘中间位置、完全无覆盖这几种情况。这些边界样例能帮你验证<=与<是否写对，也能验证倒序遍历是否真的从最上层开始。竞赛中的 WA（wrong answer）很大比例来自边界，养成构造边界样例的习惯能救你很多次。

第三，也是最重要的一点：代码越短，越要写清楚思路。P1003 的 AC 代码总共不到 20 行，但如果你不先在草稿纸上画清楚几层地毯的覆盖关系，直接上手写代码，很容易在遍历顺序上犯浑。我见过一些朋友把循环写成for (int i=1; i<=n; i++)，然后内部再记录一个最大值，虽然最后也能 AC，但代码的可读性和逻辑清晰度远不如倒序遍历。这其实是一种“用复杂度换安全感”的思路，在简单题里无所谓，到难题里就会成为累赘。

如果你现在正处在刚学会基础语法、开始刷洛谷的阶段，我建议你做完这道题后，再试着做几道同类型的矩形覆盖或区间覆盖题目，比如 P1003 的变体、P1047 校门外的树等，体会一下“从正着模拟到倒着判断”的思维转变。这种转变不是一蹴而就的，但一旦完成，你再面对“地图染色”“反推状态”这类问题时会觉得游刃有余。回头再看这道题，你会明白：洛谷里的每一道题，哪怕是绿的，都值得你慢下来，好好拆一拆。