企业官网建设流程全解析

这次模拟赛的三道题放在一起，算得上一个完整的高强度训练包：FMT、分治NTT、树剖套线段树加可删除堆，三块都是考试里容易出但平时容易被忽略的东西。第一天拿到题的时候我还挺自信，结果第一题就差点把FMT当FWT写，第二题边界调了大半个小时，第三题直接被"可删除堆"这个组合锤懵。

把这三题完整复盘一遍之后，我最大的感受是：这三个算法单独拿出来都能讲清楚，难就难在怎么在考场有限时间内快速识别题型、选对工具，还得保证实现细节不翻车。这篇就把三题从题目特征、原理推导到代码模板、踩坑记录整个走一遍，希望对正在备赛的人有点帮助。

1. 第1题 FMT：从集合幂级数到子集卷积

1.1 题目长什么样，凭什么想到FMT

第一题给了一个非常明显的信号：全集大小m不超过20，要算一个形如

h[S] = sum over T subset S of f[T] * g[S - T]

的式子，其中S是某个集合，T是S的子集，S - T表示差集。这种形式在集合幂级数里叫子集卷积，说人话就是：两个定义在集合上的函数做卷积时，交集必须为空，并集正好是目标集合。

为什么看到m <= 20就能想到FMT？因为m = 20意味着全集有2^20种子集，大约100万级别的状态数。直接枚举T和S，做3^20次运算约等于35亿次，在竞赛时限里完全不现实。而快速莫比乌斯变换处理的是子集和/超集和这类"全体子集统计"的问题，复杂度是O(m * 2^m)，m=20时算出来大约是2000万次操作，刚好能卡进时限。

有个细节值得先提醒：FMT解决的是"或卷积"和"子集卷积"两个不同的问题。"或卷积"要求A∪B=S，允许A和B有交集；"子集卷积"要求A∩B=∅且A∪B=S。很多新手（包括我）第一次看到子集卷积就直接套FMT的或卷积模板，结果答案偏大，就是因为没做交集为空的限制。

1.2 FMT的正变换和逆变换：就是高维前缀和

先回顾一下FMT本身的定义。对定义在子集上的函数f，它的快速莫比乌斯变换F定义成：

F[S] = sum over T subset S of f[T]

这本质上就是"每个集合对所有包含它的超集做贡献"的逆方向，也就是高维前缀和。写成迭代代码非常短：

// n是二进制位数，len = 1 << n for (int i = 0; i < n; ++i) for (int mask = 0; mask < len; ++mask) if (mask & (1 << i)) f[mask] = (f[mask] + f[mask ^ (1 << i)]) % MOD;

注意循环顺序：外层枚举二进制位，内层枚举mask。这个顺序不能反，因为我们要做的是"先把第0位的前缀和做完，再做第1位"，如此类推，最后得到每个状态对其所有子集的和。如果把内外层反过来，就变成了普通的一维前缀和嵌套，后果是整个变换结果完全不对。

逆变换其实就是正变换的逆运算，把加法换成减法：

for (int i = 0; i < n; ++i) for (int mask = 0; mask < len; ++mask) if (mask & (1 << i)) f[mask] = (f[mask] - f[mask ^ (1 << i)] + MOD) % MOD;

因为正变换是"累加子集"，逆变换就是"逐个撤销子集贡献"，形式和正变换几乎一样，只是加的符号反过来。

搞懂这两段代码，其实FMT的核心就已经掌握。它和FWT的区别在于：FWT处理按位与、按位或、按位异或这类位运算卷积，变换规则里带符号或者特殊组合；FMT只处理子集包含关系，形式上就是一个高维前缀和。所以见到"子集求和""超集求和"这类关键词，优先想FMT；见到"按位或卷积"这种带位运算的，再考虑FWT，两者别混。

1.3 子集卷积为什么要按照popcount分层

直接用FMT的正变换、逐点相乘、逆变换，只能解决"或卷积"的问题，也就是允许A∩B非空。但题目要求的"交集为空"其实就是要求|A|+|B|=|S|。这个约束用集合大小来表示，比用集合内容来判断好处理得多。

于是就有了子集卷积的标准套路：按照集合大小（popcount）分层。具体做法是：

• 对每个k从0到m，记f_k[S]为：如果popcount(S)=k，则f_k[S]=f[S]，否则为0。g同理。
• 对每一层分别做FMT正变换。
• 对每个状态S，把不同层的FMT结果做卷积：h_k[S]等于所有满足i+j=k的f_i'[S]*g_j'[S]之和。
• 最后对h_k做逆FMT，得到真正的子集卷积结果。

代码大概长这样：

int pc[1 << 20]; for (int mask = 0; mask < len; ++mask) pc[mask] = __builtin_popcount(mask); vector<vector<int>> f(m + 1, vector<int>(len)), g(m + 1, vector<int>(len)); for (int mask = 0; mask < len; ++mask) { f[pc[mask]][mask] = A[mask]; g[pc[mask]][mask] = B[mask]; } for (int k = 0; k <= m; ++k) { FMT(f[k], len, 1); FMT(g[k], len, 1); } vector<vector<int>> h(m + 1, vector<int>(len)); for (int mask = 0; mask < len; ++mask) for (int i = 0; i <= m; ++i) for (int j = 0; i + j <= m; ++j) h[i + j][mask] = (h[i + j][mask] + 1LL * f[i][mask] * g[j][mask]) % MOD; for (int k = 0; k <= m; ++k) FMT(h[k], len, -1); for (int mask = 0; mask < len; ++mask) ans[mask] = h[pc[mask]][mask];

这里有个容易迷糊的地方：为什么FMT之后的逐点相乘向量就是卷积？因为FMT是线性变换，且它的核心性质是把"子集卷积"在同一点S上变成了"对应FMT值的乘积"。在对每个popcount层做完FMT后，同一状态mask处的f_i[mask]和g_j[mask]相乘并累加，等价于对原函数做带大小限制的卷积，最后逆变换回收。

说到底，分层解决的是"交集为空"这个硬条件。如果不分层，两个集合如果共享某个元素，它们的并集大小会小于大小之和，而这个信息在纯或卷积里被掩盖了。

1.4 考场实现最容易踩的几个坑

第一坑：把FMT的加法逆变换写成"减完再取模"时忘了加MOD，导致负数残留。C++的取模对负数不是我们想要的语义，必须写成(x - y + MOD) % MOD。

第二坑：popcount数组别现场反复算，直接预处理。虽然__builtin_popcount很快，但在2^20量级里乘上多次枚举，累积开销也不小，预处理一维数组后所有访问都是O(1)。

第三坑：注意层数数组的空间占用。m+1层，每层2^m个int，m=20时就是21100万4字节大约84MB，勉强能过，但需要留意内存限制。如果内存紧，可以只开两个二维数组f、g，h复用f的空间，滚动更新，能省掉不少。

第四坑：子集卷积里的逆变换只对h_0到h_m整体做，不要漏层。漏一层的结果就是某些大小的集合算出来是错的，而且因为是模意义下，调错很难肉眼发现。

我当时就是没分大小，直接把原数组FMT、逐点乘、逆FMT，样例里恰好有几个小集合没测出问题，提交后WA得很惨。后来冷静下来把"交集为空"这个条件转换成"大小和等于并集大小"，才想起来要分层。

2. 第2题 分治NTT：把O(n^2)递推压到O(n log^2 n)

2.1 递推式的识别是第一步

第二题给的是一类很典型的计数递推：

f[i] = sum_{j=0}^{i-1} f[j] * g[i - j]

其中f是待求序列，g是已知序列。这种形式在组合计数里非常常见，比如卡特兰数、各种生成函数递推、DP优化等。一个朴素的想法是直接双层循环，O(n^2)的复杂度，当n到1e5级别时直接爆炸。

看到"前面所有项乘上距离相关函数，累加到当前项"这种结构，脑子里应该立刻弹出一个关键词：卷积。如果把f看成一个未知数列，g看成一个已知数列，那么右边的求和本质上就是f和g在位置i处的卷积值。可问题是f自己还没算完，这就是"半在线卷积"——后面的值依赖前面的值，两者纠缠在一起。

这时候分治NTT就是最自然的选择。它有一个非常接地气的外号叫CDQ分治套NTT，思路和CDQ分治解决偏序问题完全一致：先算左边的f，再用左边算好的f去更新右边的f，最后递归处理右边。

2.2 CDQ分治套卷积的完整流程

假设我们要计算f[0..n-1]，其中f[0]已知，递推关系是f[i] = sum f[j]*g[i-j]。分治的想法很简单：

1. 分治到区间[l, r]，如果l == r就返回。
2. 令mid = (l + r) / 2。
3. 先递归处理左半区间[l, mid]，递归结束之后，f[l..mid]就全部算好了。
4. 计算这部分f对右半区间[mid+1, r]的贡献。对于右半区间的某个位置i，它需要累加来自f[l..mid]里j的贡献f[j]*g[i-j]。注意这里i-j的范围不会超过r-l，所以只需要把f[l..mid]和g[0..r-l]做个卷积，截取需要的部分加到右半区间上。
5. 递归处理右半区间[mid+1, r]。

伪代码：

void solve(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; solve(l, mid); int len = 1; while (len <= r - l) len <<= 1; vector<int> a(len), b(len); for (int i = l; i <= mid; ++i) a[i - l] = f[i]; for (int i = 0; i <= r - l; ++i) b[i] = g[i]; NTT(a, len, 1); NTT(b, len, 1); for (int i = 0; i < len; ++i) a[i] = 1LL * a[i] * b[i] % MOD; NTT(a, len, -1); for (int i = mid + 1; i <= r; ++i) { f[i] = (f[i] + a[i - l]) % MOD; } solve(mid + 1, r); }

注意这里卷积的第i项代表的是sum_{j=0}^{mid-l} f[l+j] * g[(i)- (l+j)]，也就是左边的f对位置i的贡献。因为b的下标是从0开始的g[0..r-l]，而a的下标对应f[l..mid]的位置偏移，所以卷积结果a[i-l]正好是位置i需要的那一项。

这个流程里有个关键点：递归必须先处理左半边，再更新右半边，最后处理右半边。如果顺序乱了，右半边的某些f值在计算时依赖的左半边邻居还没算好，整个结果就错了。

2.3 复杂度分析为什么是O(n log^2 n)

每一层分治，区间总长是n。在区间[l, r]内部做NTT，复杂度是O((r-l) log (r-l))。考虑整个递归树，每一层的所有区间加起来，NTT的总规模是O(n log n)。递归树的层数大约是log n，所以总复杂度是O(n log^2 n)。

这个复杂度在n=1e5时约等于1e5 * 17 * 17，也就是差不多3000万次操作量级，NTT常数虽然比普通运算大一些，但在时限2秒左右的题目里还是能跑的。如果把卷积用FFT实现，会多一层浮点误差和精度问题，竞赛里一般直接上NTT，模数用998244353这种原根为3的质数。

2.4 边界和细节才是真正的坑

分治NTT的坑主要集中在几个地方。

第一个坑是卷积数组的长度。很多模板喜欢把长度设成2的幂，但到底要多长？这里有一个非常隐蔽的问题：a的下标范围是0到mid-l，b的下标范围是0到r-l，两者相乘时，卷积结果最高下标是(mid-l) + (r-l)。但实际上我们只需要用到i-l这一项，而i最大是r，所以最大用到r-l。为了保证卷积不循环卷积（即不发生环回叠加），长度len必须大于卷积的有效长度。常规做法是len开到大于(r-l+1)的2的幂，至少是两倍长度，否则做NTT会得到循环卷积的错误结果。

第二个坑是对f数组先清零。在递归进入solve(l, r)之前，右半边的f可能是上次某个兄弟区间更新过的残余值。如果不清零，就会把不该算进来的贡献也加进去。通常做法是在每一次更新前先把右半区间的f清零，或者在主函数中统一清干净。

第三个坑是g数组的访问范围。递推式里j从0到i-1，所以g的下标范围是1到i。但分治里为了统一，b数组填的是g[0..r-l]，其中g[0]一般是0（因为j=i时f[j]*g[0]这一项不应当出现）。如果g[0]非零，结果就会多出一项f[i]*g[0]，也就是自己贡献自己，这在分治NTT里是不允许的。写转移的时候最好特殊处理一下，或者把g[0]置为0再进循环。

第四个坑是模数不是NTT友好模数时怎么办。如果题目给的是1e9+7这种不能做NTT的模数，就只能用三个NTT模数分别做，再用中国剩余定理合并。这个步骤很容易写错，建议敲模板时直接封装好三模NTT，而不是在考场上临时拼。

我这次就在第二个坑上面摔了一跤：右半区间没有清零，结果第二次递归进来的残留值叠加在正确答案上，样例能过但数据一大就挂。后来在更新前加了fill清零，问题立刻消失。

3. 第3题 毒瘤树剖套线段树+可删除堆：把"删除"嫁接到链上最值

3.1 题意还原：到底在维护什么

第三题我愿称之为本次模拟的压轴。题目给了一棵带点权的树，要求支持两类操作：

• 修改某个节点的权值；
• 查询从x到y的路径上，权值最大的节点是谁，并且要支持反复修改、反复查询。

第一眼看上去，树链剖分加线段树搞个区间最大值就能解决，复杂度O(log^2 n)。问题出在题目的附加条件：查询的是"删除某个指定节点后，这条路径上的次大值"，而且这个指定的节点每次都可能变化，操作次数又多。这就意味着我们不能只维护一个区间最大值，还得能够快速剔除某个点之后查到新的最大值。如果每次查询都暴力把被删除节点的权值改成极小值，查询完再改回来，遇到连续大量查询就直接TLE。

于是就有了"线段树节点维护可删除堆"的思路：线段树的每个节点不再只存一个最大值，而是维护一个候选集合，这个候选集合里存的是当前区间内经过某些筛选后的有效值。当要删除某个点时，不是真的把这个点从线段树里物理删除，而是往对应堆里打入一个"删除标记"，查询时通过堆顶的惰性删除跳过无效元素。

3.2 树链剖分：把路径问题拆成区间问题

树链剖分的作用是把树上路径操作变成"若干连续区间"的操作。具体做法是先用两遍DFS求出每个点的深度、子树大小、重儿子，然后把重儿子优先的DFS序作为线段树的下标，这样一条重链上的点在DFS序上是连续的，就可以用线段树维护链上的区间信息。

对一次查询路径x到y：

• 不断比较x和y所在链头的深度，深度大的那个链先整体作为一个区间处理；
• 通过点往上跳到链头的父节点；
• 直到x和y在同一条链上，最后处理这个收尾区间。

单次路径查询会拆出O(log n)个区间，每个区间在线段树上再做O(log n)的查询，所以树剖本身给的是O(log^2 n)的复杂度。这部分算基本功，真正麻烦的是线段树里维护的东西比普通最大值多。

3.3 可删除堆的实现：两个优先队列的障眼法

"可删除堆"这个名字听起来唬人，实现起来却非常简单。C++的priority_queue不支持删除任意元素，我们就在它外面套一层"待删除堆"：

struct DelHeap { priority_queue<int> keep, del; void push(int x) { keep.push(x); } void erase(int x) { del.push(x); } int top() { while (!keep.empty() && !del.empty() && keep.top() == del.top()) { keep.pop(); del.pop(); } return keep.empty() ? -INF : keep.top(); } };

原理一句话：lazy deletion，也就是延迟删除。插入时正常往keep里塞，删除时先把被删元素塞进del，等到查询堆顶时，如果keep的堆顶恰好等于del的堆顶，说明这个堆顶已经被删了，就把keep和del同时弹出，直到堆顶不再是已删除元素。

这里有个小坑：如果存在重复元素，删除一个值可能对应堆里有多个相同值。上面这个写法里，keep.top() == del.top()时，每次弹一对，能保证如果删了一个x，那么只要堆顶还是x，就会被连续弹走。如果这个x还有剩余有效副本，那它仍然会出现在堆顶。注意erase的时候没有校验x是否真的存在某个有效副本，如果删了一个根本没插入的值，可能会导致堆顶被错误清除。所以实际使用时要么保证操作合法，要么在删除前判断一下当前top()是否等于x，等于才删。

3.4 线段树每个节点挂一个堆：整体是怎么拼起来的

回到第三题。如果我们只对整条路径做全局最大值，普通线段树就够。但要支持"临时删除某个点后问最大值"，就需要在区间查询时跨过那个点。朴素在线段树里做"跳过某个点"很难，因为一个点可能同时属于很多个线段树节点。

换一个角度：不需要在线段树查询时动态跳过，而是在每个线段树节点里，把左右子树的答案收集到一起，用可删除堆来维护"当前节点区间的候选答案"。这样当某个叶子节点的权值发生变化时，从叶子到根的所有祖先节点都能及时更新自己的堆。查询时逻辑保持不变，只是把"取区间最大值"替换成"取对应节点的堆顶"。删除某个点时，给对应叶子及所有包含它的祖先节点的堆打入删除标记，这些祖先的堆顶就会自动让出，暴露出下一个最大值。

完整操作流程：

1. 修改节点u的权值为v：

   • 在线段树中找到u对应的叶子位置，更新实际权值；
   • 从叶子向上递归，每个祖先节点push新值、erase旧值；
   • 同时更新全局堆（如果题目要求维护整棵树的答案）。

2. 查询路径x到y的最大值：

   • 树剖拆出O(log n)个区间；
   • 线段树区间查询，每个被完全覆盖的节点直接返回该节点堆的top()；
   • 把这些候选值再取max，就是路径答案。

3. 查询路径x到y但不允许选节点z作为答案：

   • 在查询过程中，凡是返回值等于z的节点，继续调用它的左右子节点分别查询，再取max；
   • 或者先在线段树路径区间覆盖查询时，对被z覆盖的所有祖先节点临时打入删除标记，查完再恢复。第二种写法要注意恢复时把删除标记也pop掉，否则堆顶会残留错误状态。

这个实现里，可删除堆的价值体现在一个微妙的时刻：当我们要"撤销删除"时，只需把对应的erase值从del堆里弹出，而要"删除"时只需push进del，整个过程不需要重算任何区间信息，比每次改动都暴力重建线段树节点快得多。

3.5 复杂度与实现细节

修改操作：线段树单点更新要走O(log n)层，每层都要做堆的push和erase，每次堆操作O(log size)，所以单次修改O(log^2 n)。查询操作：树剖分解O(log n)个区间，每个区间线段树查询O(log n)，取堆顶O(1)，所以也是O(log^2 n)。总复杂度在n和操作次数同为1e5级别时可以接受。

实际操作中还有三个细节必须注意。

第一个细节是线段树的每个节点都开一个DelHeap对象，内存开销极大。如果一棵线段树有4n个节点，每个堆默认构造又要分配底层容器，内存很容易爆。解决办法是只对真正用到堆的节点按需初始化，或者用vector< priority_queue > 配合reserve提前分配。

第二个细节是修改点权时要同时维护"真实值"和"候选堆"。真实值存在线段树叶子节点的basic数组里，用于单点更新时判断旧值；候选堆存的是经过合并后的答案集合。两者不能混用，否则删除旧值时找不到原始值。

第三个细节是查询时如果某一段区间整个被删除节点覆盖，直接返回堆顶可能拿到被删元素。最稳妥的写法是：在线段树query递归时，进入某个完整覆盖的节点之前，先判断这个区间的"区间最值是否等于被禁止节点"；如果是，就往下继续拆左右子树，直到叶子或者左右值不再等于禁止节点。

我真的在这次踩了个大坑：一开始没有给每个节点单独开堆，而是全局只搞了一个堆，结果删除一个点之后所有查询都串味了。后来想明白，树剖把空间拆成一维，线段树把时间拆成区间，而可删除堆解决的是"集合内元素动态增删"这一层抽象，三者各管一摊，少一个都不对。

4. 赛后的一些体会

三道题全复盘完之后，我个人最大的收获不是某个模板，而是"识别题型"这件事比"背诵模板"重要得多。FMT那道题，只要看出子集卷积并想到分层就能做；分治NTT那道题，认出半在线卷积就会想起CDQ套NTT；树剖套线段树加可删除堆那道题，最关键的其实是想明白"临时删除某个点"不能靠朴素线段树解决，必须引入带惰性删除的堆。

另外分享一个考场上的小技巧：如果肉眼无法确定某个算法的复杂度能不能过，就用数据范围反推。看到2^20级别就优先想集合幂级数和FMT；看到1e5递推直接排除O(n^2)；看到树上一堆修改加查询，树剖跑不掉，重点考虑如何改造线段树节点里的维护对象。数据范围是最诚实的提示，比任何经验都好用。

还有一个我反复吃亏的地方：代码里凡是出现(a - b) % MOD这种负号运算，务必转成(a - b + MOD) % MOD；凡是NTT数组长度不确定，就多开一倍。这些坑都不是算法问题，但每次考试都会带走几十分钟的调试时间。把常见的坑提前写进自己的代码模板注释里，比考场上临时翻博客强得多。