爆标：SCP-2026 func 做到线性

GY程袁浩 · 2026-10-18 21:34:42 · 题解

前言

Another Sol 由我独立在赛时获得，接下来的结构性质推导都是由 GPT 进行的。本文是用笔者的语言介绍一遍整个算法的流程。这在线线性做法也太诡异了。

介绍一下这题的 O(n) 做法。

在开始之前，我们不妨介绍本题的另外一种解法。

如果你想看 GPT 写的版本，请看这个，如果你在阅读我的讲解的时候遇到了困难可以试试，至少看起来非常详细，但是也太长了。

Another Sol

我们常规化地考虑枚举端点，枚举右端点考虑左端点在不同位置的时候对答案的贡献。依照套路，我们考虑拆位。

考虑左端点往左移动的过程。

考虑第 k 位，考虑或值的贡献，一定是构成了一个分界点，左边全是 1，右边全是 0。

再继续考虑 \text{mex} 的贡献，当 [0,2^{k}-1] 的数都齐全的时候 \text{mex} 达到至少 2^{k}，如果后面 \text{mex} 变大了，那么必然出现过一个 2^{k}，因此当 \text{mex} 第一次取到至少 2^{k} 的时候，后面的数同样会变成 1。

因此最后得到总形式一定是一个分界点前面都是 1，后面都是 0，这样我们只需要找到这个分界点，就能刻画贡献了。

不难发现上述值的分界点是容易寻找的，难点在于寻找 \text{mex} 的分界点，问题变成询问 [0,2^{k}-1] 的数上一次出现最早的数在哪。我们显然可以使用数据结构两只 \log 维护，不过这是倍增的结构，因此我们可以直接在规整的线段树上从叶子往上跳就能 O(1) 回答每位，这样我们就做到了 O(n\log V)。

Observation

我们需要回答 [0,2^{k}-1] 的最小值，令 P_{k} 为 [0,2^{k}-1] 中上次出现位置的最小值，一开始 P_{k}=0，\text{last}_{i} 为数字 i 上一次出现的位置。

我们把区间划分为 B_{k}=[2^{k-1},2^{k}-1]（k=0 时将 2^{k-1} 视作 0）。

对于 B_{k} 里面出现次数最少的数字 x，假设 m=2^{k}。

假如 x 当前在 t 出现，在下一次出现之前，对于新加入的数 y，如果加入之前 \text{last}_{y}>t，那么将不会改变 P_{k} 的值。由于这段区间加入的数位置全都 >t，而 \text{last}_x=t，因此每个数最多改变一次 P_{k}。因此最多改变 m 次。

由于 x 的一次出现最多会带来 m 次贡献，假设 x 出现 f_{x} 次。因此总贡献一定不超过 mf_{x}。设 B_{k} 总出现次数为 F_{k}，由于 x 是出现最少的数字，因此 f_{x}\frac{m}{2}\le F_{k}，因此得到 f_{x} 是 O(\frac{F_{k}}{m}) 的，所以改变次数一定不超过 O(\frac{F_{k}}{m}\times m)，这是 O(F_{k}) 的。

这里 k=0 的时候有额外情况，但是容易说明复杂度同样是正确的。

又由于 B_{k} 互不相交，所以 F_{k} 加起来最多是所有数出现次数的和，最终就可以得到变化次数是 O(n) 的。

Continue

首先区间或和有著名的线性做法，我们先套用那个做法，然后统计额外贡献。以下只考虑额外贡献算法是否在线。

设 Q_{k} 为位置最大的点，使得第 k 位是 1。那么第 k 位的额外贡献就是 2^{k}\times \max(P_{k}-Q_{k},0)，记 D_{k}=\max(P_{k}-Q_{k},0)，我们希望维护 D_{k} 的加权和。先考虑计算 P_{k}。

利用刚才观察，我们可以做很多事情。比如说我们直接维护每个 B_{k} 的最值，然后直接往后合并，只要我们及时退出，复杂度就是线性！具体来说，我们对于每个 B_{k} 维护一个链表，一开始加入 B 集合中的每个值加入一个 0，每次加入一个数 x 的时候在链表中删除上次出现的位置，然后把当前位置塞到链表尾部，每次链表头部就是最小位置。当一个 B_{k} 原本为 x 的值被更新，我们从 j=k 开始遍历，设 b_k=\min_{x \in B_{k}} \{\text{last}_x\}，维护一个 t=\min_{i \le j}\{b_{i}\}，如果 t\le x 了，说明对于 k'\ge j，P_{k'} 都不会被这次修改影响，因此直接结束循环，否则直接用 t 覆盖 P_{j} 的值，这里 t 在一开始直接赋值为 P_{k-1}（k=0 特判），后面看着改即可，由于这里改的 P_{j} 都是会变化的，因此复杂度是对的。

然后接下来考虑维护 Q，这里不能直接维护，否则复杂度不对，所以我们只考虑修改会造成贡献的 Q_{k}。考虑加入目前的数造成的贡献变化，首先我们是改大，所以如果 D_{k}=0，加入当前数并不会让贡献发生任何变化。而会变化当且仅当 P_{k}>Q_{k}，这需要 P_{k} 在上次 Q_{k} 修改后有一次修改，由于 P_{k} 的修改总共是 O(n) 次的，所以根据势能分析，这样的变化也只有 O(n) 次。我们只需要用一个二进制状态维护哪些 k 的 D_{k}>0，和当前数取并（二进制意义下与），然后扣出这个二进制里为 1 的位置暴力修改就对了。

当然，Q 带来的影响不止加入数的时候修改 Q 的影响，当我们修改 P_{k} 的时候，同样需要得知当前 Q_{k} 的值，不过我们还是没必要直接维护所有 Q，这里如果忽略询问本身的性质，可以抽象成：询问前 p 个数中，最大的位置使得该位置值的第 k 位为 1。如果我们能回答这个询问那么就可以正确维护加权和了。

解决这个问题的三种方法

O(n \log \log n) 在线做法

为了解决这个问题，我们可以将原序列分成 \Theta(\log n) 长度每块，对于每块建立线段树，对于一棵线段树就可以在线段树上花费 O(\log \log n) 的时间二分来找到这棵线段树的某个范围内最后一个第 k 位为 1 的点。然后记录对于每一块，考虑前面的最后一个第 k 位为 1 的块，这里的处理加上初始化是 O(n+\frac{n}{\log n} \times \log n)=O(n) 的。每次询问我们首先对于块内线段树二分查询 \le p 中最后一个第 k 位为 1 的点，如果不存在我们就跳到处理的块再线段树二分即可。这个处理方法允许我们在线 O(n \log \log n) 的解决整个问题。

O(n) 离线做法

由于 P 被修改的询问并不依赖之前询问的值，因此我们可以直接先做一遍 P 修改的过程把询问扣出来，然后离线处理。

具体的，我们从右到左扫序列，这样子只要遇到一位 k 的询问能回答，那么当前位置就是答案。我们在过程中利用二进制维护哪些 k 已经有询问，对于每个 k 维护一个询问队列，加询问的时候插入，直接取并（二进制意义下按位与）把为 1 的扣出来回答询问队列里面的询问就行了。

最后得到询问的答案之后，我们再跑一遍原算法此时就直接知道每个询问的答案了。这样就做到了 O(n)。

O(n) 在线做法

利用询问本身的性质。事实上，我们没有必要在每次询问的时候都重新求 Q_{k}。具体的，我们记录 q_{k} 为上一次求 Q_{k} 的时候或者在新插入数 Q 时按照 D_{k}>0 修改的 Q 值，q_k 初始值是 0，以下描述“查询时候”的 D 值是未考虑当前数的，P_{k} 始终使用新值。如果询问 Q_{k} 的时候有 D_{k}>0（这里 D 是修改 P 之前的 D，说明 q_{k} 是准确值，因为其在使得 D>0 的那次 P 修改中一定进行了真实询问，且后面 Q 都没有再被改过）或者 q_{k} \ge P_{k}，那么可以直接回答 q_{k}（不一定是准确值，但 Q_{k} 的值会不断增大，所以这里无论是否是真实值都不会有贡献），否则，我们将证明，剩余的情况只有 O(\frac{n}{2^{k}}) 种。

考虑相邻的三次真实 Q 查询，假如时间分别为 t_{1}<t_{2}<t_{3}，我们将证明 t_3-t_1\ge 2^{k}。以下分两种情况讨论：

• 如果 (t_1,t_2] 出现了第 k 位为 1 的数

那么第二次查询之后一定有 q_{k}>t_1，又由于在 t_3 时 P_{k}>q_{k}，所以 P_{k}>t_1，这说明 [0,2^{k}-1] 的数在 [t_1+1,t_3] 全部出现了一遍，所以 t_3-t_1>2^k。

• 如果 (t_1,t_2] 没有出现第 k 位为 1 的数

那么第二次查询之后一定有 P_{k}>q_{k}=Q_{k}，这说明 D_{k}>0，由于 t_3 查询时 D_{k}\le 0，所以 [t_2+1,t_3] 一定出现了一个第 k 位为 1 的数，此时 q_{k} 被更新为 q_{k}>t_2，又由于 t_3 时又有 P_{k}>q_{k}，所以 P_{k}>t_2，同样可以说明 t_3-t_1>2^{k}。

又由于第一次查询 Q 的时候必须满足 P_{k}>q_k，此时 q_k\ge 0，因此 P_{k} > 0，因此之前必然出现了至少 2^{k} 个数。

因此 t_3-t_1\ge 2^{k}。由此可以得到 Q 查询次数是 O(\frac{n}{2^{k}}) 的。

这里你需要知道一个求和式

这里为什么就不讲了，如果不知道可以自己算一下。

利用这个式子，我们就知道，如果对于单个询问，我们都可以花 O(k) 的时间求出来，最终花的时间就是 O(n)，那怎么做到单次询问 O(k) 呢？

我们考虑一个类似线段树的结构，具体的，我们每隔 2^{k} 分一块，那么这样一共只有 O(n) 块，合并是 O(1) 的。

这里是一个分块形式例子，对于 n=8，

我们再在每个块内维护块内所有值的按位或，以及 H(k) 表示最右边的完整 2^{k} 长度块使得块内所有值按位或第 k 位为 1。

每次加数我们考虑如果当前长度为 n，那么若 2^{k}\mid n，我们就需要合并两个 2^{k-1} 的块作为一个 2^{k} 的块，具体我们从 2^{0} 开始不断增加 k 直到不整除。以及记得同时维护 H(k)，注意 k=0 是直接加当前点，不需要合并。这创建了一个块，因为块数是 O(n) 的，所以加数总和复杂度为 O(n)。

每次询问 k，首先从右向左遍历目前没有到 2^{k} 的块（如 k=2,[1,4],[5,8],[9,10],[11,11]，这里 [9,10],[11,11] 就是散块），如果这些块内的所有数的按位或的第 k 位为 1，我们就像线段树二分一样递归到这些块的内部的小块最后就可以找到了。否则我们直接访问 H(k)，找到那一块，在内部继续线段树二分即可，如果 H(k) 不存在，那么答案为 0。这样由于散块最多 O(k) 个，且每次二分都是在最多长度为 2^{k} 的块内二分，所以最多检查 O(k) 个节点，因此单次询问 O(k)。

特别的，这里当 k=0 的时候单次询问 O(1)。

至此，我们就做到了单次询问 O(k)，因此总时间复杂度就 O(n) 了。