企业官网建设流程全解析

前两天刷题，碰到一道编号P7282的题目，题面短得让人放松警惕，结果我在上面耗了一整个晚上。题名叫Hop，意思就是“跳”，但真正让我卡住的不是跳这个过程，而是怎么快速知道“从每个位置出发，到底要跳几次才能出界”。

问题本身很简单：一排位置，每个位置带一个整数，如果右侧存在某个位置j，使得这两个数的二进制按位与不为0，那么你会自动跳到满足条件的最靠左的那个j；如果右侧根本没有这样的位置，那么一次Hop之后你就直接跳出整行，游戏结束。题目要求把每个位置作为起点，算出跳跃次数。n可以到十万级别，暴力写法轻松TLE，突破口就两个：一个叫拆位法，一个叫分块。这两个词听起来像是两套独立技术，但在这道题里它们是前后脚配合的关系——拆位法负责快速求出每个点下一次跳到哪，分块负责把“一路跳下去”这个过程压缩起来。

这篇文章我会从暴力思路讲起，拆开拆位法的原理，再用手算例子把分块跳表的过程捋一遍，最后给出完整可用的代码实现和一些调试心得。适合刚学完分块、正在刷普及+难度题目的读者，也适合想搞清楚“为什么所有题解都在用拆位法”的选手。

1. 题面到底隐藏了什么

先把这个“Hop”规则说得再具体一点。假设有一个长度为n的数组a，下标从1到n。从任意起点i开始：

• 找到最小的j，满足j > i且(a[i] & a[j]) != 0，跳到j；
• 如果不存在这样的j，算一次跳跃，直接结束；
• 输出从每个起点出发，到跳出数组为止的总跳跃次数。

注意这里说的“一次跳跃”包含了最后那下出界。比如从某个位置出发，右侧没有共同二进制位，那答案就是1，不是0。这个细节很多人在算样例时会差1，后面对拍时最容易暴露。

初看这个题，很多人会直接写两层循环：对每个i，从i+1往后扫，找到第一个满足位与非0的位置，然后沿着这个后继一路跳。问题是每个位置最多可能往后扫O(n)个位置，每个起点又要跳O(n)次，理论上限就是O(n²)。n稍微大一点，比如五万十万，直接凉透。

那有没有办法让“找下一跳”变成O(1)或者O(log)级别的操作？有，这就是拆位法。

在展开拆位法之前，可以先想一个问题：为什么这道题跟二进制位有关系，而不是直接比较大小？因为位运算的“匹配”天然适合按位拆分。你要判断两个数按位与是否非0，不需要看完整两个数，只需要看看它们是否存在某一位同时为1。反过来，如果某一位上两个数都是1，那它们一定匹配。这就是拆位法的全部出发点。

2. 拆位法：用last数组把“找下一跳”变成常数代价

2.1 核心观察

判断a[i]和a[j]是否有共同位，等价于判断是否存在某一位k，使得a[i]和a[j]的第k位同时为1。

那么这个条件就被拆成了若干个独立子条件：a[i]的第0位是否为1且a[j]的第0位是否为1；a[i]的第1位是否为1且a[j]的第1位是否为1；以此类推。只要其中一个子条件成立，整体就成立。

于是我们可以把问题转化成：对于当前起点i的每个为1的位，我都想在右侧找一个“该位为1的位置”。如果有多个这样的位置，取下标最小的那个，因为题目要的是“最靠左的j”。最后再在所有位对应的候选中取最小值，那就是答案。

这里有一个很关键的反直觉点：每一位只要保存一个候选位置就够了。很多人会想“万一某个更靠左的位置虽然这一位是1，但其他条件不满足呢？”其实不用慌，因为我们只关心当前i的固定为1的那些位。每一位都提供了一个独立的“匹配资格”，最终的匹配点是所有资格里面的最靠前者。保存每一位的“最靠前候选”就已经足够了。

2.2 倒序扫描的过程

拆位法用到的数据结构简单得让人意外：一个大小为B的数组last，B是二进制位数，一般取30或31。

从右往左扫描整个数组。当扫描到位置i时：

1. 先查询：枚举a[i]所有为1的位b，取last[b]的最小值，记为nxt[i]。如果这个最小值是n+1（表示右侧没有该位为1的位置，后面会解释），就说明没有合法下落点；
2. 再更新：把a[i]所有为1的位b的last[b]设置为i。

为什么要先查询再更新？因为如果先更新，last[b]里就会包含当前位置i自己，于是nxt[i]可能会变成i，形成自环。这个错误我第一次写的时候就踩了，查了半天才发现是先更新再查询导致的。

关于last[b]到底存的是什么：它表示【当前已经扫描过的、位于右侧的所有位置中，第b位为1且下标最小的那个位置】。由于扫描方向是从右往左，越新遇到的位置下标越小，所以直接用i覆盖last[b]就行，不需要比较。

举个例子。设n = 7，a = [2, 3, 1, 2, 5, 4, 1]，二进制表示如下：

倒序扫描。初始化last[0..2] = 8（n+1，表示未出现）。

• i=7，a[7]=1，第0位为1。查询：last[0]=8，nxt[7]=8。更新：last[0]=7。
• i=6，a[6]=4，第2位为1。查询：last[2]=8，nxt[6]=8。更新：last[2]=6。
• i=5，a[5]=5，第0、2位为1。查询：min(last[0]=7, last[2]=6) = 6，nxt[5]=6。更新：last[0]=5，last[2]=5。
• i=4，a[4]=2，第1位为1。查询：last[1]=8，nxt[4]=8。更新：last[1]=4。
• i=3，a[3]=1，第0位为1。查询：last[0]=5，nxt[3]=5。更新：last[0]=3。
• i=2，a[2]=3，第0、1位为1。查询：min(last[0]=3, last[1]=4) = 3，nxt[2]=3。更新：last[0]=2，last[1]=2。
• i=1，a[1]=2，第1位为1。查询：last[1]=2，nxt[1]=2。更新：last[1]=1。

得到的nxt数组是：nxt[1]=2，nxt[2]=3，nxt[3]=5，nxt[4]=8，nxt[5]=6，nxt[6]=8，nxt[7]=8。

其中8就代表“下一次直接跳出数组”。

2.3 为什么这个取最小值是正确的

需要稍微严谨一点。设a[i]的所有为1的位组成集合S。对某个位b∈S，右侧所有第b位为1的位置集合记作P(b)，last[b]是P(b)中的最小下标。

所有可能匹配点的集合就是所有P(b)的并集。这个并集里的最小元素，一定等于某个last[b0]（因为整体最小值一定属于某个P(b0)，而last[b0]又是P(b0)里的最小值，所以整体最小值不可能比last[b0]小，也不可能取不到）。所以直接取所有last[b]的最小值，就是右侧第一个与a[i]有共同位的位置。

这个证明想明白之后，拆位法就没有秘密了。它本质上是用30个桶，把“两个数匹配”这个关系压缩成“单边某位是否出现过”。

2.4 边界和注意事项

• 如果a[i]等于0，它没有任何一个位为1，查询结果自然是n+1，直接跳出，代码里不用特判；
• 位宽B要跟数值上限匹配。a[i]范围如果到1e9，30位够用；如果开了long long，记得B取到60以上，否则高位判断会漏；
• 代码里访问last[b]之前，一定要确保b在0到B-1之间。很多人的错误是把(a[i] >> b) & 1写成a[i] & (1 << b)，然后忘记处理b=31时左移溢出的问题。

3. 分块：把“一路跳下去”变成一次跳一整块

3.1 有了nxt为啥还不够

现在每个位置都已经知道自己的下一跳是谁，剩下的问题就是：从每个起点出发，沿着nxt一直走，直到越过n+1，总共要走多少步。

最直接的做法是对每个起点模拟，遇到nxt值大于n就停。最坏情况下，比如数组严格递增且相邻两个数都有共同位，那么从1出发要跳n次才能出界，对n个起点都这么做就是O(n²)。

一个自然的想法是倍增：预处理up[k][i]表示跳2的k次方步到达哪里，查询时倍增累加。静态情况下，这个做法确实更好，复杂度O(n log n)。但很多Hop类题目的变体会把规则改成“跳过的位置会被删除”，一旦中间某个点被拿走，后续所有经过它的倍增路径都会失效，只能大面积重构。分块的做法在这种场景下要稳得多：修改只影响某一个块，其他块的跳表仍然有效。

所以这里选分块，不是因为它比倍增更高级，而是因为它更“皮实”，并且实现起来非常直白。这也是这个题题解普遍把拆位法和分块并列的原因——拆位法解决单个后继，分块解决多次跳跃的加速。

3.2 块内跳表：cnt和out

把下标1到n按块大小S分成若干块，块大小通常取√n。对每个位置i，维护两个信息：

• cnt[i]：从i出发，直到第一次跳到当前块外面去，总共需要跳几次；
• out[i]：从i出发，第一次跳出当前块之后，落在哪个位置。如果直接跳出数组，out[i]=n+1。

这样设计的好处是：查询从任意位置出发时，不需要一步一步走，先按cnt跳到块外，再在下一个块里继续累加。每个块最多经过一次，所以单次查询最多走O(n/S)步。

3.3 预处理的具体写法

预处理顺序很重要：必须从每块的右端点向左处理。因为nxt[i]一定大于i，如果nxt[i]也落在当前块内，那么nxt[i]一定在i的右边，而右边的位置在这一轮已经算好了，可以直接拿来做转移。

如果nxt[i]落在当前块内：

• out[i] = out[nxt[i]]
• cnt[i] = cnt[nxt[i]] + 1

如果nxt[i]落在当前块外，或者nxt[i]=n+1：

• out[i] = nxt[i]
• cnt[i] = 1

这就是整道题最核心的转移方程。注意第二种情况里，cnt固定为1，表示“跳一次就离开当前块（或者离开数组）”。

还沿用前面的例子，n=7，a=[2,3,1,2,5,4,1]，已经求出nxt：

取S=3，块1是[1,3]，块2是[4,6]，块3是[7,7]。

先处理块1，从右往左：

• i=3，nxt[3]=5，不在块1内，所以out[3]=5，cnt[3]=1；
• i=2，nxt[2]=3，在块1内，所以out[2]=out[3]=5，cnt[2]=cnt[3]+1=2；
• i=1，nxt[1]=2，在块1内，所以out[1]=out[2]=5，cnt[1]=cnt[2]+1=3。

块2：

• i=6，nxt[6]=8，不在块2内，out[6]=8，cnt[6]=1；
• i=5，nxt[5]=6，在块2内，out[5]=out[6]=8，cnt[5]=2；
• i=4，nxt[4]=8，不在块2内，out[4]=8，cnt[4]=1。

块3：

• i=7，nxt[7]=8，out[7]=8，cnt[7]=1。

得到块内跳表：

查询从1出发：ans += cnt[1] = 3，x变成out[1]=5。5仍≤n，ans += cnt[5]=2，x变成out[5]=8。x=n+1，停止，答案5。手动模拟一遍确实是1→2→3→5→6→出界，正好5次。

查询从3出发：ans += cnt[3]=1，x=5；ans += cnt[5]=2，x=8；停止，答案3。模拟路径是3→5→6→出界。

可以明显看到，分块就是把同一块内的连续几步压缩成一步，代价仅仅是预处理时多花O(n)的时间。

3.4 块大小怎么选

如果你只需要输出所有起点的答案，查询阶段总复杂度是O(n * n/S)，预处理阶段是O(n)，拆位阶段是O(nB)。所以总复杂度大概是：

要让n²/S和nB平衡，取S=√n是比较稳的选择。实际实现时，我习惯写成int S = sqrt(n) + 1;，因为整数开根后向下取整可能导致S偏小，多1个能避免一些边界问题。

如果n是1e5，B=30，√n≈317，n²/S≈3.15e7，再乘上常数，现代机器上是可以轻松跑完的。如果你发现总时间偏紧，可以把S调大到400~500，减少查询次数，但要小心块内转移链变长，预处理耗时反而可能增加。这类题的常数问题，最好的办法就是拿不同S去实测。

4. 完整代码实现

下面这份代码可以直接复制使用。用的是1-indexed，比较贴近题目习惯。这里我统一默认数组元素范围在1e9以内，所以位宽B=30，但如果输入可能出现2^30以上的数，记得调大B。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } const int B = 30; // 根据 a[i] 上限调整 vector<int> nxt(n + 1, n + 1); vector<int> last(B, n + 1); // n+1 表示“右侧不存在该位为1的位置” // 拆位法：倒序扫描，先查询，再更新 for (int i = n; i >= 1; --i) { int best = n + 1; for (int b = 0; b < B; ++b) { if ((a[i] >> b) & 1) { best = min(best, last[b]); } } nxt[i] = best; for (int b = 0; b < B; ++b) { if ((a[i] >> b) & 1) { last[b] = i; } } } int S = (int)sqrt(n) + 1; int m = (n + S - 1) / S; // 块数 vector<int> blockId(n + 1); for (int i = 1; i <= n; ++i) { blockId[i] = (i - 1) / S + 1; } vector<int> L(m + 1), R(m + 1); for (int b = 1; b <= m; ++b) { L[b] = (b - 1) * S + 1; R[b] = min(n, b * S); } // out[i]：第一次跳出当前块后的落点，n+1表示出界 // cnt[i]：跳出当前块所需的跳跃次数 vector<int> out(n + 1), cnt(n + 1); for (int b = 1; b <= m; ++b) { int l = L[b], r = R[b]; for (int i = r; i >= l; --i) { int to = nxt[i]; if (to <= n && blockId[to] == b) { out[i] = out[to]; cnt[i] = cnt[to] + 1; } else { out[i] = to; // 可能是另一块中的位置，也可能是n+1 cnt[i] = 1; } } } for (int i = 1; i <= n; ++i) { int x = i; int ans = 0; while (x <= n) { ans += cnt[x]; x = out[x]; } cout << ans << '\n'; } return 0; }

几个实现细节再强调一下：

• n+1这个哨兵值贯穿全程，代表“跳出数组”。所以last初始化为n+1，nxt初始化为n+1，out也会落到n+1；
• 更新last时，直接赋值而不是取min，因为倒序扫描保证了新位置的下标一定更小；
• 在判断nxt[i]是否和i在同一块时，必须先判to <= n，否则blockId[n+1]越界；
• 查询循环里，x每次变成out[x]，由于out[x]严格大于x（如果x <= n），不会死循环。这个严格递增的性质非常关键。

5. 常见问题与调试实录

5.1 为什么last存的是“最小下标”而不是“最大下标”

这是拆位法最绕的地方。因为我们是从右往左扫，先遇到的是下标更大的位置，后遇到的是下标更小的位置。每次遇到某位为1就覆盖last[b]，所以最后last[b]留下来的一定是已经扫描过的所有位置中下标最小的那个。而我们要找的是右侧第一个匹配点，也就是下标最小的，方向正好对上了。如果反过来从左往右扫，那last[b]就变成保存最大下标了，查询逻辑得整个翻转。

5.2 先查询还是先更新

必须先查询再更新。我第一次写的时候，先执行了更新，结果所有nxt[i]都变成了i自己，跑出来的答案全是1。原因很简单：当前位置i自己的第b位也是1，更新完之后last[b]就变成i了，查询时自然把自己当成了“右侧”的候选点。

5.3 最后跳出那一下算几次

算一次。我在前面反复强调，是因为很多人模拟时习惯“从i跳到j才算一次”，到最后一步没有合法j时容易忘记计数。统一处理方式就是：nxt[i]=n+1时，cnt[i]=1，out[i]=n+1。这样所有情况都有统一的转移方程，不会串味。

5.4 位宽设置不当导致漏算

如果输入数据有大于2^30的数，B=30会漏掉高位。建议看题目的数据范围，如果a[i]可以是int的全部范围，B至少设31；如果开了long long，B最好设63。写(a[i] >> b) & 1比a[i] & (1 << b)更安全，不会出现1 << 31这种直接UB的情况。

5.5 块大小S和边界

S取sqrt(n)+1基本没问题。但要注意块数m = (n + S - 1) / S，最后一块的元素个数可能少于S，预处理循环用L[b]到R[b]就能覆盖。查询时while (x <= n)一定会退出，因为x每次跳到out[x]，而out[x]要么是更大的下标，要么是n+1。

5.6 对拍是最后的安全网

这种题思路不难，但细节极多。我强烈建议写一个O(n²)的暴力版，然后随机数据对拍。具体来说：生成n在1到20之间的随机数组，对每个起点暴力模拟求出标准答案，再和分块版答案对比。我第一次对拍时就发现上面说的“先更后查”自环问题，以及最后一步计数差1的问题。对拍代码不用很讲究，能跑就行，但一定要跑够几百组随机数据。

6. 扩展：如果跳跃条件更复杂

拆位法的适应性很强。如果题目把条件改成“跳到右侧第一个满足(a[j] & a[i]) != 0且a[j] > a[i]的位置”，在拆位法的基础上还要解决一个“大于”的限制。这时可以用值域分块或者权值线段树去维护“某个值域范围内最近出现的位置”，配合位的条件一起查询。但拆位法的核心思想不变：把一个数的某一位单独拿出来处理。

如果条件反过来，要求“跳到右侧第一个与a[i]没有共同位的位置”，就不太适合用当前的“30个last取min”套路，需要改成维护“某一位为0的最近位置”，逻辑上会更绕一些。所以拿到题第一件事，是看清楚是“有共同位”还是“没有共同位”，方向不同，维护的信息完全不一样。

还有一类题会问“从每个点出发，按规则跳跃，经过多少步会回到某个已访问的点”，也就是跳转图成环。这种情况下分块依然可以处理：块内跳表记录了出块位置，如果存在环，出块位置会永远达不到，这时可以配合判环处理。我在另一个模拟题里就是这么拆的。

7. 最后分享一点实际体会

这道题我做完之后最大的感受是：拆位法本身不难，难的是你能不能在关键时刻想到“把一个整数按位拆开，每一位单独维护最近出现位置”。很多涉及位运算匹配的题，本质都是这个套路。而分块这个部分，反而让我觉得踏实，因为它的思路非常朴素，出问题也容易排查。

如果你正在刷题，建议不要只背这题的结论，而是拿纸笔把上面那个小样例手算一遍拆位过程，再手算一遍分块跳表。把“先查后更”和“cnt/out从右往左转移”这两个关键点彻底想明白，以后再遇到类似题，你会顺畅很多。我就是这样从“题解看得懂”变成“下次能自己写出来”的。