1. 先辨别一下标题这里的cf到底是不是穿越火线搜索框里输入“cf 981 div3 c”你大概率会先看到一堆跟算法竞赛毫无关系的东西穿越火线蹲跳跳蹲上箱子宏、C语言字符串逆序输出、C盘清理命令大全、松下CF-ZR6驱动下载……总之没一个指向编程竞赛。这也没办法中文互联网里 cf 和 c 两个词的歧义太大了几乎所有以 c 开头的内容都能蹭上。不过经常打 Codeforces 的人应该一眼就懂cf 是 Codeforces981 是比赛场次编号Div3 是这场比赛的参赛组别最后的 c 指的是 Div3 里的第三题。所以这篇文章要聊的就是 Codeforces Round 981 Div. 3 的 C 题。为了防止有人误会我一开始就把话说清楚。这场 Div3 给我的整体印象是A、B 两题基本是送分题C 题开始有区分度。C 题表面上是一道关于矩阵网格的模拟题实际上考的是坐标变换和差分计数恰好是很多只会写暴力的选手最难受的题型。如果你正在刷 Div3 练手这篇文章值得看完因为我会把从读到解的完整链路拆开讲还会写几个我在赛场上踩过、赛后复盘才发现有多蠢的坑。2. 题面到底在算什么射线、对角线、覆盖次数2.1 射线是怎么走的我先按比赛时读到的题面描述来复述一下。Sakurako 有一张 n×m 的网格初始时每个格子的值都是 0。接下来有若干条射线每条射线从网格某条边界的某个格子出发沿对角线方向直线前进直到碰到另一条边界才会停下来。每经过一个格子这个格子的值就加 1。最后给出若干询问每个询问给一个格子的坐标要求输出这个格子最终的数值。如果没见过这类题第一反应通常是开一个二维数组把每条射线扫过的格子逐个加 1最后查询。这个思路本身没错但数据范围不允许——n 和 m 都可能接近 2×10^5询问和射线数量也都接近这个量级。单条射线在最坏情况下要经过 O(min(n,m)) 个格子总复杂度大约是 O(射线数 × min(n,m))在 2×10^5 级别下基本跑不完。所以这道题的信号非常明显不能一个格子一个格子地加必须成段地加。至于怎么成段得先看清楚射线的运动规律。2.2 射线只走两类对角线在一个矩形网格里沿对角线方向走只有两种可能从左上到右下也就是 \ 方向从右上到左下也就是 / 方向。方向不同射线所在的“轨道”就不同它们之间永远不会互相干扰。这里有个很关键的性质\ 方向上任意两个格子的行号减列号 i - j 是同一个值/ 方向上任意两个格子的行号加列号 i j 是同一个值。比如一个 3×3 的网格里位置 (0,0)、(1,1)、(2,2) 都属于同一条 \ 对角线因为它们的 i - j 都等于 0而 (0,2)、(1,1)、(2,0) 都属于同一条 / 对角线因为它们的 i j 都等于 2。这就是整道题的切入点与其在二维平面上模拟不如把每条对角线看成一个一维数组射线在这个一维数组上做的操作就是“覆盖了一段连续区间”。连续区间加值能想到什么差分。2.3 暴力复杂度估算为什么必须放弃模拟用具体数字感受一下。假设 n 2×10^5m 2×10^5射线数量 q 2×10^5。最坏情况下每条射线都要穿过矩阵的对角线长度接近 2×10^5。直接模拟就是 4×10^10 次格子更新这个数据量在任何评测机上都跑不动。但如果转换成“每条对角线上的区间覆盖”每个射线只需要在对应对角线上记录两个端点事件总事件数只有 2q也就是 4×10^5 级别再配合前缀和还原复杂度一下子就压到 O((n m q) log q) 甚至 O(n m q)这才是能过的算法。3. 关键一步用两个隐藏坐标把对角线拉直3.1 坐标变换公式与偏移处理要把对角线当成一维数组首先得给每条对角线一个唯一编号。对于 \ 方向编号取 u i - j。问题在于 C 数组下标不能是负数所以实际使用时要加一个偏移量。u 的范围是 -(m-1) 到 n-1加偏移 m-1 之后编号范围变成 0 到 nm-2总共有 nm-1 条 \ 方向对角线正好是网格里主对角线总数。对于 / 方向编号取 v i j范围是从 0 到 nm-2本来就不是负数直接拿来当数组下标即可不需要额外偏移。这里我建议把两个方向分开存不要混在一个数组里。原因后面踩坑部分会详细说。3.2 让每个格子都能定位到自己的两条对角线有了编号规则每个格子 (i,j) 就能唯一确定两条对角线主对角度编号k1 i - j (m - 1)副对角线编号k2 i j下面是一个 3×4 网格的示例方便对照公式格子坐标 (i,j)i - j主对角线编号 k1 i-jm-1副对角线编号 k2 ij(0,0)030(0,3)-303(2,0)252(2,3)-125从这个表能直观看到k1 和 k2 的取值范围都是 0 到 nm-2但含义完全不同。格子的最终值就是它所在的主对角线被覆盖的次数加上它所在的副对角线被覆盖的次数。3.3 射线怎么投影成区间每条射线都落在某条对角线上覆盖的是这条对角线上的连续一段格子。我们还需要把“连续一段格子”翻译成“一维区间”。我的做法是用行号 i 作为这条对角线内部的“位置坐标”。因为对角线上的格子行列号是单调同步变化的选行号还是列号都可以只要整条对角线内部保持一致就行。拿 \ 方向举例。一条射线从 (x,y) 出发沿右下方向走。如果 x y说明出发点靠左射线会一路走到下边界如果 x y说明出发点靠上射线会一路走到右边界。不管哪种情况这条射线所在主对角线的编号是固定的 k1 x - y (m - 1)它覆盖的行号区间就是从 x 到终点行号之间的连续段。/ 方向的射线同样处理唯一需要注意的是这个方向的行号可能从大往小变比如从下边界出发往上走时行号是递减的。所以在打差分之前一定要把区间的左端点换成较小的行号右端点换成较大的行号保证区间方向统一否则差分前缀和会完全错乱。4. 差分数组是怎么打上去的核心代码与实现细节4.1 事件差分而不是完整差分这里有个实现细节值得单独说。网上很多题解喜欢写“把每条对角线拉直存进数组”听起来很高大上但如果真开一个 vectorvector 把每条对角线上所有格子存下来空间总和还是 n×m在 2×10^5 级别的行列下直接内存爆炸。正确做法是只存“差分事件”。一个区间 [l, r] 的加 1 操作拆成两个事件位置 l 处 1位置 r1 处 -1。每个射线只产生两个事件总事件数只有射线数量的两倍空间开销非常小。具体来说我给每个方向开一个 vector下标是对角线编号里面存一堆 pairpair 的第一位是“行号位置”第二位是差分增量。射线覆盖的区间加进来之后最后统一对每条对角线的事件按位置排序扫一遍做前缀和就能还原这条对角线上任意格子的覆盖次数。4.2 核心代码框架下面这段是核心框架不是完整提交代码考试时主体逻辑按这个写就行const int MAXD 2e5 5; // ev1 存主对角线方向\ev2 存副对角线方向/ vectorvectorpairint, int ev1(MAXD * 2), ev2(MAXD * 2); // 主对角线方向编号 id覆盖行号区间 [l, r] void add_main(int id, int l, int r) { if (l r) swap(l, r); ev1[id].push_back({l, 1}); ev1[id].push_back({r 1, -1}); } // 副对角线方向编号 id覆盖行号区间 [l, r] void add_sub(int id, int l, int r) { if (l r) swap(l, r); ev2[id].push_back({l, 1}); ev2[id].push_back({r 1, -1}); } // 处理射线把每条射线换成对应方向上的一个区间加 // 例如一条 \ 方向射线先算出主对角线编号 k1再算出行号区间 [L, R] // add_main(k1, L, R); // 查询阶段把每条对角线的事件排序二分找目标行号 int query_main(int id, int pos) { auto v ev1[id]; sort(v.begin(), v.end()); // 严格小于 pos 的事件累加值才是覆盖到 pos 的射线数 int sum 0; for (auto [p, d] : v) { if (p pos) break; sum d; } return sum; }实际提交时肯定还要优化一下查询效率不能每条查询都从头扫事件。这里展示的是最直观的写法方便理解原理。优化也很简单把每条对角线上的查询点也按位置排好序和事件一起双指针扫描一次就能算出该对角线上所有查询点的答案。4.3 查询阶段注意“边界位置”的语义差分数组的经典约定是在 r1 处放 -1表示区间 [l, r] 在 r 之后结束。所以查询位置 pos 的覆盖次数是所有位置小于 pos 的事件增量的总和。这里有一个很多人会写错的点如果事件里出现位置恰好等于 pos 的 -1它不应该被计入 pos 的覆盖次数因为那个 -1 表示的是上一个区间的结束边界。最简单的方法就是二分pos - 1位置之前的前缀和或者扫描时遇到 p pos 就停下。代码里我用的是扫描到 p pos 就 break逻辑上等价但对每条查询独立扫描会慢实际写的时候建议把所有查询离线处理。5. 我在这题上踩过的坑偏移、方向和数据类型5.1 坑一主对角线编号忘记加偏移量这是我第一次写这类题最喜欢犯的错。i - j 在不是 0-indexed 的小数据下看着没问题但一旦出现 i j 的格子编号就是负数拿去当数组下标直接越界。本机可能不报错交上去就是玄学 RE。修复方式很简单不管矩阵长什么样一律用 k1 i - j (m - 1)把范围硬生生平移正。错误表现原因修复本地随机小数据能过大数据 REi-j 出现负下标统一加 m-1 偏移样例中某一列的结果不对偏移算错一位用 3×4 小网格手推一遍编号我给自己定的规矩是只要涉及矩阵坐标变换先写一个小矩阵把所有编号打印出来对了再继续写下面逻辑。多花两分钟能省半小时调试。5.2 坑二区间没统一方向就打了差分副对角线方向有个容易忽略的地方一条 / 方向的射线如果从下边界出发向上走覆盖的行号范围在逻辑上是“终点行号到起点行号”也就是一个递减区间。如果直接按起点行号和终点行号当成左端点右端点打出来的差分区间是反的。我在第一次写的时候加了下面的判断if (l r) swap(l, r);就这么一行写完后样例全过。没有这一行你的前缀和会在后半段完全错位而且数据越随机越难查因为它不是稳定地错而是错得毫无规律。5.3 坑三把主对角线和副对角线的贡献混在一个数组里这个坑更隐蔽。看起来 k1 和 k2 的取值范围都是 0 到 nm-2好像可以共用一个差分数组。但它们是两套完全不同的坐标系即使编号相同代表的也不是同一条线。打个比方主对角线编号 3 是网格里从左上往右下数第四条斜线副对角线编号 3 是从右上往左下数第四条斜线。两者可能交叉在某个格子上但在同一个差分数组里它们的事件会互相污染。正确姿势是像我前面代码那样分开存储查询时把两个方向的覆盖次数相加而不是在存储阶段混在一起。5.4 数据类型该用 long long 的地方别省射线数量在 2×10^5 级别时单格子的覆盖次数最多也就是 2×10^5int 完全够用。真正需要 long long 的是计算 n×m 这类中间值的时候比如判断暴力是否可行或者某些推导过程中出现 n×m 的临时变量。我习惯把所有和网格尺寸相关的计算直接声明成 long long虽然这题用不上但防止下一题就是 10^18 的数据范围。6. 从这道C题往后看Div3 的“坐标变换”题该怎么练6.1 这场B题也是对角线题有意思的是这场 Div3 的 B 题 Sakurako and Water 同样在对角线上做文章。B 题要求找出每条 \ 方向对角线上最小的负数把它变成 0求总共需要多少次操作。做法就是扫描每条对角线统计负数的处理和。这两题串起来看出题人的意图很明显先让你在 B 题里熟悉“对角线就是一组 i-j 相同的格子”这件事然后在 C 题里把对角线升级成区间覆盖计数。如果你只是单题单做可能感觉不到这个设计如果你按场次横向复盘就会发现在同一个知识点上B 和 C 是很好的阶梯组合。6.2 坐标变换题的通用三步这类题不管外表怎么换核心套路其实是固定的。第一步把特殊结构映射成常规的一维问题。对角线用 i-j 和 ij环形数组用取模树结构用欧拉序本质都是找一个合适的坐标系让操作变成区间或前缀和。第二步把每个操作拆解成映射后空间上的区间操作。一条对角线上的一段连续格子在一维数组里就是一个区间一圈环形数组的一段在取模坐标里也是一个区间。第三步用差分、前缀和或者树状数组去维护这些区间最后按查询还原答案。绝大部分 Div3 的 C/D 题都逃不出这个框架。6.3 给还在刷 Div3 的同学三条实在建议第一不要满足于“看出是差分”。差分在不同结构上的变形非常多一维差分、二维差分、树上差分、对角线差分建议都亲手写一遍。特别是对角线差分在 CF 里出现的频率不低自己完整实现一次比看十篇题解都管用。第二比赛时如果 C 题卡住果断先写个暴力对拍。这题暴力其实很好写直接开二维数组模拟每条射线的轨迹。有了暴力生成随机数据对拍能高效抓出边界条件的致命错误比自己盯代码肉眼 debug 强太多。第三时间分配要果断。Div3 前 30 分钟如果 C 题还没有成型思路可以先读一遍 D 题。很多时候 D 题反而是模板套路题C 题留给后面的时间慢慢磨。我自己在赛后习惯给每场 Div3 的 C 题打一个题型标签比如这题就打上“坐标变换 差分覆盖 对角线”。积累十几场之后你会明显发现 C 题能卡住人的点就那么几个以后见到相似的题第一眼就能定位解法。