椰程信奥 · 限时训练单

专题6·前缀和与差分（二） · 限时训练单（50 分钟 · A/B 双卷）

训练说明

项目	内容
题量	2 题：地毯（二维差分） CARPET ／激光炸弹 LASER
时长	50 分钟。闹钟一次设定，不暂停、不查资料、不回看课件。
分层	A 卷＝冲满分路线；B 卷＝保部分分路线。由教练按上次成绩分派，学生不自选。
纪律	时间到立即停手并提交。没写完的正解也要先把当前能过的版本交上去。
集训定位	5 天集训第 3 天 · 建模线（T2 拉分）

时段	时间	做什么	做完的标志
第 1 段	0–5′	两题全部读一遍，在题号旁写下「这题像哪种模型」和「我先拿哪一档」	两行字写完
第 2 段	5–22′	第 1 题：先写能过小数据的暴力版，再改正解	样例过了、暴力版留着
第 3 段	22–40′	第 2 题：同上，先保第 1、2 档	样例过了
第 4 段	40–47′	对拍：小数据把暴力版与正解版跑同一批随机输入，比对 200 组	0 组不一致
第 5 段	47–50′	提交前 60 秒自检（见第四节）	四条全部打勾

唯一硬规定：时间盒一到就换下一题，哪怕正解只差一行。复赛里「四题各拿 60 分」永远胜过「一题 100 分、三题 0 分」。

地毯（二维差分）（CARPET）：四角 d[x1][y1]+=1, d[x1][y2+1]−=1, d[x2+1][y1]−=1, d[x2+1][y2+1]+=1 再二维前缀和　易错：四个角的符号别写反；数组开到 n+2
激光炸弹（LASER）：二维前缀和 + O(1) 查询每个 R×R 子矩阵，取 max　易错：边长 R 的正方形覆盖 [x, x+R−1] 不是 R+1；边界要取 min(n, x+R−1)
必做：每题都留一份暴力版，用它造小数据对拍 200 组，0 不一致才算过。

题目	先拿档位	具体动作	封顶时间
地毯（二维差分）	特判 → 暴力 → 特殊性质	`n == 1` → 只有那一个矩形是 1；每张地毯逐格 +1，n ≤ 1000、区域 ≤ 1000² 稳过；所有地毯都是 1×1 → 就是二维计数，不用差分	12′
激光炸弹	特判 → 暴力 → 特殊性质	`R == 1` → 就是单格最大值；目标点全在 R 内 → 直接输出总和；枚举每个格子为左下角逐格求和，R ≤ 10、坐标 ≤ 5000 稳过；R 覆盖整个区域 → 直接输出总和	12′

B 卷不要求满分，要求"零爆零"：每题都至少有输出、都不 RE、都不编译失败。先保证这件事，再回头补正解。

✓	检查项	典型翻车
☐	数据范围：int 会不会溢出，要不要 long long	样例过了、大数据爆 0
☐	边界情形：n = 0 / 1、空输入、最大值，各手算一遍	特判档自己写错
☐	文件名与读写：是否 freopen、多测时数组有没有清空	本地对、提交 0 分
☐	本讲最易错：二维差分四个角的 ± 号写反，`y2+1` / `x2+1` 漏写	整题思路对、一分拿不到

档位	预期分	做法	耗时
① 特判档	5–10	n == 0/1、全为 0、已有序等极端情况直接输出	2′
② 暴力档	20–30	多重循环 / DFS 全枚举 / 朴素 O(n³)，不优化，保证小数据全对	8′
③ 特殊性质档	40–60	针对部分测试点的性质单独写一份（规模小、值相同、类型单一）	10′
④ 正解档	100	本讲算法 + 与暴力版对拍验证	15′+

题目	得分	丢在哪一档	具体原因（写现象，不写"粗心"）	下次动作
地毯（二维差分）
激光炸弹

批阅规则：丢分原因必须写成可执行的现象（例如"递推下标差了一位"），禁止出现"粗心""没看清"这类无法产生下一步动作的词。

洛谷	题名	年份组别	难度	与本讲的关系
P8816	上升点列	CSP-J 2022	普及+/提高	同类思维：坐标 + 排序（近年很少单独考二维前缀和）

加练规则：只做与本讲对应的那一道，做完照样走四档阶梯（先特判 → 再暴力 → 再特殊性质 → 最后正解），并且必须写暴力版对拍。真题的价值在于"考法"，不在于"多刷"。