蔡德仁随笔：~一些 OI 教学研究的故事~

问题求解

知识点不只有算法

2017 年，距今七年之前——当时省选的主流 OJ，BZOJ 因故暂停服务，我作为一个学生参与 LibreOJ 的创建。在起初添加题目标签系统时，我们感觉到“OI 中似乎有两类不同的知识点”，然而，谁也说不清楚两者到底是什么，只好草草归结为“一般的理论或思想”和“具体的有模板题的知识点”，这就是 LibreOJ 玫红色和草绿色两种标签的由来。

时过境迁。大学二年级起，我们学习了一般的算法设计、计算理论。许多曾经模糊的、玄之又玄的思想和理论渐渐有了它清晰的面貌和数学上明确的表达与应用。那时，我意识到 OI 中确实存在两类不同的知识点——但不是什么宽泛和具体的对立，这二者的分野对研究算法和解决问题没什么意义。OI 中真正的区别在于组合模型与算法，也就是问题研究对象的结构和算法问题本身的性质。

例如这个经典例子：一个长为 $n$ 的序列 $\{a_i\}$ 每一项是 $1\dots m$ 之间的整数，给定若干个限制，每个限制的形式是 $l,r,u,v$ 表示 $a_{l\dots r}$ 这一段的最大值必须在 $[u,v]$ 内，问方案数。

这个问题的形式是统计方案数。最基本的做法是尝试判定一个特定的方案是否满足条件。这里，我们研究的是数学对象是序列上一些区间的最值。序列区间最值的结构是笛卡尔树——因此我们在笛卡尔树上的 LCA 处检查限制。于是，我们就找到了一种按照遍历笛卡尔树的顺序逐位判定某个方案是否满足条件的算法。直接对这个判定算法过程的状态压缩就可以得到一个递推（DP）算法统计方案数。也就是 $f(i,j,k)$ 表示区间 $a_{i\dots j}$ 最大值为 $k$ 的方案数，转移顺序表示最值结构（笛卡尔树的形状），再进行优化。

这里，问题求解有几个步骤： - 问题研究的组合对象：序列区间最值结构→笛卡尔树 - 根据笛卡尔树容易得到朴素的判定算法 - 问题形式-计数：从判定到计数→DP的基本方法状态机-状态压缩 - 算法优化：经典的DP优化方法，状态合并、数据结构（前缀和等）

可以看到，这里存在两个知识点：“笛卡尔树”刻画序列区间最值结构，“递推/DP DP优化”在之后解决计数问题。换言之，OI中存在刻画问题的组合对象以及算法形式两个主要任务，它们是不同的。

问题在于，传统的OI训练完全是以算法形式（算法模板、模式、优化技巧）来组织的——因为只有算法会有模板题，组合对象在传统教学中不存在。除了笛卡尔树等少数，绝大多数的组合知识点尽管重要，却完全被忽略，只能在所谓的“杂题选讲”，DP/贪心/构造题单中寻得只鳞片爪。更严重的是，表示、推导、研究组合模型性质结构的方法几乎没有任何系统学习的意识。大半的NOI金银牌在半天内做不出任何有三、四个引理的组合推导问题（比如这样的）。对于那些没能从同学交流或自学组合数学悟出道理的多数同学来说，七年前和今天都是如此。

除了组合，一切没在算法模板题和经典教科书注册了位置的的数学也都如此被忽略。例如 OI 中这个常见的推导：最大化绝对值和 $\max(\sum \lvert x_i-y_i\rvert)$。

$$ \begin{aligned} &\max(\sum \lvert x_i-y_i\rvert)\\ =&\max(\sum \max(x_i-y_i,y_i-x_i))\\ =&\max(\sum \sigma_i(x_i-y_i))\\ \end{aligned} $$

将绝对值（或者曼哈顿距离、方差等类似的东西）写成参数最值，然后利用最值方向的一致性通过变量分离等简化最优化权值的范围/形式。本来，这个出现次数不少的技术也应当是一个知识点，但传统教学中学生很难意识到这一点。这导致不管是自己做题，还是题单、选讲等课程都很难避免学习中遗漏和忽略这类方法。

因此，在教学中传达这些现代数学的研究意识是必要的。任何的关键点、难点都应该被研究。例如 OI知识点的字段和类型所写的。为了达到这一点，一些笔头的算法数学的练习、研讨也是必要的。

数学语言与一句话题解

《西江月·证明》 ——佚名

即得易见平凡，仿照上例显然。

留作习题答案略，读者自证不难。

反之亦然同理，推论自然成立。

省去过程QED，由上可知证毕。

每个 OIer 大概都有过对着题解抓狂的时刻。面对“单调性一下就行了”“注意到可以二分图染色并给白色权值异或1”……种种一句话题解，如同见到了一座精致的牙雕，但是谁又能想象出生长它的大象的样子呢。

对于个人笔记，一句话题解记录的是问题中的关键认识。表面上看，一句话题解看不懂可能有数学符号的含义没有标明，跳过表述等原因。但更多的问题在于，这个性质的前因后果是什么？（谁具有这个性质？哪里用到这个性质？）它的数学目的是什么？（能解决什么问题？没有为什么不行？有/无这个性质的区别是什么？）它能否推广到其它的情况？（改条件还成立吗？对于其它模型、问题能否诱导出类似的？）

这些是研究数学问题的一般方法。我们希望自己能通过一点例子举一反三，那么不妨试一试从这个例子中的关键点开始研究。

在今年的江苏省队集训（有四五个 NOI 金牌的同学参加）中，我出了自认为难度接近的 3 道题目，但实际结果却有些出乎预料。3 道题中有一道好几个同学会做，但另外 2 题却没人得出正确的思路。和同学讨论了想法和做法的细节后，我注意到这样一个事实：我们研究问题的思维方式是不同的。同学们做题的时候，往往找到问题的一个大概的模型（比如二维点、树上路径、二分图、生成函数等某个比较宽泛的对象）之后，根据自己的解题经验观察和尝试该模型上适用的算法模式/技巧（比如对于树上路径来说，尝试按LCA分类/启发式合并、树上差分、分治、倍增等手段），将其套入问题看是否能够满足条件和性质或联想做过的类似问题算法做些调整。

这一做法的问题是，对问题研究对象本身没有稳定的刻画，在不断尝试过程中，之前推导的性质观察往往被浪费。一次又一次地“重做”这道题，直到某个幸运时刻猜对了大体的做法，然后利用题感和经验完成细节工作。这对于整体不太经典（即使每个部分的推导都很常规）的问题就很难做了——甚至很多处理方法相当直接的问题都被称为 Ad-hoc。

举一个例子。有一排 $n$ 条鱼体型为正整数 $\{a_i\}$，可以让一条鱼吃掉另一条相邻的，体型不大于自己的鱼，并且体型加上被吃的鱼的体型。每次问一个范围，问里面哪些鱼能吃光范围内的其他所有鱼。

首先，容易发现，任何时候一条鱼的状态对应一个区间。然后，只有那些“极大”的，也就是无法继续吃掉左右相邻鱼的区间是有用的。到这里，我们作为“题感”选手迅速发现了一个事实：每次从极大区间跳到一个更大的极大区间，区间和（鱼大小）至少翻了一倍，容易得到总的层数是 $\log a$ 的。

到此为止——我们可以轻易用倍增、线段树等算法配合 $\log a$ 的势能来在可接受的时间复杂度内解决问题。然后 AC，下一题。

然而，等等。这时候我们对问题的认识足够充分吗？

想想一般方法。我们应该刻画问题的研究对象，并且不断加深对它的认识。对于这个问题来说，上面我们已经得到了刻画问题的关键是极大区间的结构。而我们容易证明：不能有两个极大区间在相交的同时互不包含。否则，假设有 $[a,c)$ 和 $(b,d]$ 两个极大区间满足这点且 $a\le b\le c\le d$，那么 $[a,c)\ge b\gt (b,d]\ge c\gt [a,c)$（这里的不等式比较的是对应的鱼体型总和），矛盾。极大区间一定满足它相邻两侧的数字比自己的区间和还要大，这会导致矛盾。

所以这是嵌套集，可以用一棵有根树的每个子树（对应的DFS序区间）来表示。上面的性质也对应了树高不超过 $\log a$ 等等。更重要的是——当我们想进一步研究这个问题时，只要研究这棵树就行了。显然，找到这棵树比起只是套用倍增、线段树解决特定问题，我们的认识深刻得多。

在一开始就刻画问题的研究对象，并不断推进认识——而不是直接尝试套用各种技巧。这是不那么依赖题感和灵感的一般方法。想想自己如果要打表找规律，该对谁打表（问题研究的关键数学对象），用什么格式输出（表示和刻画它的可能手段）。

题感做题就像盲人摸象，反复探索各个部位，不同局部性质难以联系，尝试很多次才能逐渐得到整体认知。而如果先知道了象的大致形态（问题的研究对象和可能的表示），再对具体的部位做研究逐步填充，局部之间是有联系的，自然探索起来事半功倍。

一句话题解令人迷惑，也往往是因为我们并不知道在问题中要刻画什么，因此缺乏目的。没有主语只有谓语，自然是读不懂文章的。反过来说，能把一句话题解的数学逻辑补全，也是一种可行的练习方式。

举一反三的计算理论

计算理论是另一个竞赛传统教学未曾意识到的部分。

问题类、归约、计算复杂性、计算模型——现在 OI 算法已经发展到了需要这些一般理论和思想的地步。具体到各类具体的算法，更一般的算法设计思想也很重要。OI 正在逐渐习惯基于组合结构的算法复杂性分析，或者基于自动机、等价类等的字符串研究（就像IOI2024D2T1）。生成函数云云更不可能被人力禁止。总之，OI 开始需要一些研究能力——而不只是学会一些经典算法和应用然后局部改编。

最近某位同学的一个问题可以作为例子：

问：有这么一个问题：删边加边MST（最小生成树），离线。使用线段树分治的前提下，存在一种并查集做法：在一个节点上，下传下来一些边，表示可能在MST里面（它们都已经完全覆盖这个节点），在这个节点上，忽略子树边，把所有完全覆盖的边掏出来，如果不在MST就永远没用。把子树边全加入，再把完全覆盖的掏出来，如果在MST就永远有用。后者缩点，前者删除，剩下的下传。

这个算法似乎有些反直觉。这个东西是否有拓展或者可能源于更加本质的某个事物？？

（思考了一段时间之后）

这里面，是否：问题的核心在于保证递归到一个节点时候的有效点/边数量？我想说，这个算法并不容易归结为最基本的mst方法和线段树分治的简单结合，而是有一点它自己的东西。它的牛逼之处在于对于复杂度的保证。而这一点，是否有推广？或者说，就可以把它当作一道孤题，不再细究？

这位同学实际上已经注意到了问题的关键。学术上，这是数据结构的一个非常基本的思想。为了解释这个问题，我们可以考虑把它推广到MST以外的其他问题上并做一个比较。

答：这个怎么推广——感觉找到一些和MST有类似性质的东西还是不难的——比如二维偏序极值（有一堆区间，要求插入区间删除区间，用线段树分治处理，维护所有不被其他区间包含的区间组成的序列，也就是所谓动态单调栈或者说动态前缀最值）。

把维护MST换成维护二维偏序极值，这个技巧还适用，但可能需要更复杂的均摊。

具体来说就是得按子树内涉及到的操作参数对数轴进行分段（值域压缩/离散化），然后把上面继承下来的潜在的极值序列坐标同属一段的缩起来处理。每一段要么同时不是极值，要么同时是极值。

核心点在于，线段树分治的一个 $m$ 大小的节点的子树内可能涉及到的操作数是最多不超过 $m$ 的（或者有些问题 $m\log m$）。而在很多问题中，$m$ 个操作实际上最多也就只能区分出 $m$ 组本质不同的信息。 就像在长为 $n$ 的序列上做 $m$ 次区间加也可以分段缩点（值域压缩/离散化）把序列规模缩小到 $O(m)$。

而MST也满足这个条件（图里只有 $m$ 条边待考虑时，图待定最小生成树的规模也可以缩到 $O(m)$ 表示），所以也可以这么做。这实际上在组合对象里是非常常见的性质，并不是MST特殊的。

所以其实大部分线段树分治都可以这样处理。这也是数据结构的一个标准方法，操作少的时候，就是可以按“能否被不同操作区分”对原来的组合对象进行缩点，使得总规模变成和数据结构操作有关的。

当然，也有不满足这个的。比如动态增删物品的背包。因为只要达到 $\log V$ 个物品信息量就是 $\Theta(V)$ 的。

这位同学很快发现了其他应用。

有一个应用：P7361 拜神。

首先这个题有一个显然的3log做法：二分，然后看区间max lcp，这个东西可以掏出来1log个支配对，再来一个log是线段树之类的。这是粗略的分析。当然实际上本题有一个优点：因为修改是1log，而查询没有log，那么二分的那个log正好补上来。所以这实际是2log。

另一种算法：整体二分。然而整体二分导致了按理来讲必须是3log。它加入支配区间，然后其实就是覆盖了一个阶梯，是二维偏序极值问题。查询本质上查询前缀最值。

然而注意到其实，询问有一个端点是不变的，所以可以在每一层的时候根据询问不变的那个端点来缩段，然后暴力维护前缀max。

分析复杂度：首先，所有节点总共本质不同的段是只有1log的。然而本来就有1log的支配对，一搭配线段树分治/（或者说整体二分，本质差不多），已经自带2log了，即便是O(1)操作，复杂度无可避免的依然是2log。

当然，这也并不是完全没用，如果询问的q改成nlogn级别，那么正常算法的二分加持久化就会导致复杂度和整体二分一样变成3log。然而这个做法复杂度依然是2log。

只要理解了数学上准确的例子，从算法设计的一般思想中受益也并不困难。

前面几节，我们讨论的是如何在例题上举一反三——而在这一节，我们展示了学习算法时计算理论的意义——在算法设计上举一反三。当例子足够时，我们总会走向一般的理论。

天涯若比邻

OI 的研究和改进是站在计算机科学基础上，许多同学和老师们在 OI 社区中无私贡献的成果。

感谢他们。而对于我来说，有一些人是特别记得的。

感谢我的朋友 ljt12138，tqyaaaang，sys.，还有 Shilling.X，以及许多人。

感谢 EI 的所有工作。

感谢 Qingyu 的所有工作。

感谢 fjzzq，command_block，YeahPotato，skc，dXqwq，xht，undefined，Menci，rxz 和许多其它同学对更科学的 OI 学习资源和技术做出的贡献。（感谢小粉兔——如果那篇归约课件已经做完了的话。）

感谢蒋炎岩老师，您提出的问题总给我们指出道路。

感谢 cxm，xudyh，wls，vfk，jiry，lrj 和其它许多前辈带我接触 OI 教研。

感谢勰码团队和 lethalboy 对教学实践的支持。

感谢我在信息之路上重要的刘老师，董老师，陈老师，段老师，姚老师。

仍然，最后引用蒋老师的话来结尾：

大部分同学都没能迈过从 “业余选手” 到 “职业选手” 的门槛——给你更多的时间，能解出非常困难的题目。如果你接受过一点理论计算机科学的训练，就会发现竞赛作为一种 “竞技体育”，其实是性价比极低的。 ——蒋炎岩 Yanyan's Wiki (jyywiki.cn)

祝各位都能从题感走向严肃、科学的研究方法，成为算法设计和计算机科学技术的“职业选手”！

liu_cheng_ao的博客

博客