前两天刷题碰到一道编号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从i1往后扫找到第一个满足位与非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位是否为1a[i]的第1位是否为1且a[j]的第1位是否为1以此类推。只要其中一个子条件成立整体就成立。于是我们可以把问题转化成对于当前起点i的每个为1的位我都想在右侧找一个“该位为1的位置”。如果有多个这样的位置取下标最小的那个因为题目要的是“最靠左的j”。最后再在所有位对应的候选中取最小值那就是答案。这里有一个很关键的反直觉点每一位只要保存一个候选位置就够了。很多人会想“万一某个更靠左的位置虽然这一位是1但其他条件不满足呢”其实不用慌因为我们只关心当前i的固定为1的那些位。每一位都提供了一个独立的“匹配资格”最终的匹配点是所有资格里面的最靠前者。保存每一位的“最靠前候选”就已经足够了。2.2 倒序扫描的过程拆位法用到的数据结构简单得让人意外一个大小为B的数组lastB是二进制位数一般取30或31。从右往左扫描整个数组。当扫描到位置i时先查询枚举a[i]所有为1的位b取last[b]的最小值记为nxt[i]。如果这个最小值是n1表示右侧没有该位为1的位置后面会解释就说明没有合法下落点再更新把a[i]所有为1的位b的last[b]设置为i。为什么要先查询再更新因为如果先更新last[b]里就会包含当前位置i自己于是nxt[i]可能会变成i形成自环。这个错误我第一次写的时候就踩了查了半天才发现是先更新再查询导致的。关于last[b]到底存的是什么它表示【当前已经扫描过的、位于右侧的所有位置中第b位为1且下标最小的那个位置】。由于扫描方向是从右往左越新遇到的位置下标越小所以直接用i覆盖last[b]就行不需要比较。举个例子。设n 7a [2, 3, 1, 2, 5, 4, 1]二进制表示如下位置数值二进制12010230113100142010551016410071001倒序扫描。初始化last[0..2] 8n1表示未出现。i7a[7]1第0位为1。查询last[0]8nxt[7]8。更新last[0]7。i6a[6]4第2位为1。查询last[2]8nxt[6]8。更新last[2]6。i5a[5]5第0、2位为1。查询min(last[0]7, last[2]6) 6nxt[5]6。更新last[0]5last[2]5。i4a[4]2第1位为1。查询last[1]8nxt[4]8。更新last[1]4。i3a[3]1第0位为1。查询last[0]5nxt[3]5。更新last[0]3。i2a[2]3第0、1位为1。查询min(last[0]3, last[1]4) 3nxt[2]3。更新last[0]2last[1]2。i1a[1]2第1位为1。查询last[1]2nxt[1]2。更新last[1]1。得到的nxt数组是nxt[1]2nxt[2]3nxt[3]5nxt[4]8nxt[5]6nxt[6]8nxt[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查询结果自然是n1直接跳出代码里不用特判位宽B要跟数值上限匹配。a[i]范围如果到1e930位够用如果开了long long记得B取到60以上否则高位判断会漏代码里访问last[b]之前一定要确保b在0到B-1之间。很多人的错误是把(a[i] b) 1写成a[i] (1 b)然后忘记处理b31时左移溢出的问题。3. 分块把“一路跳下去”变成一次跳一整块3.1 有了nxt为啥还不够现在每个位置都已经知道自己的下一跳是谁剩下的问题就是从每个起点出发沿着nxt一直走直到越过n1总共要走多少步。最直接的做法是对每个起点模拟遇到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]n1。这样设计的好处是查询从任意位置出发时不需要一步一步走先按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]n1out[i] nxt[i]cnt[i] 1这就是整道题最核心的转移方程。注意第二种情况里cnt固定为1表示“跳一次就离开当前块或者离开数组”。还沿用前面的例子n7a[2,3,1,2,5,4,1]已经求出nxt位置nxt12233548566878取S3块1是[1,3]块2是[4,6]块3是[7,7]。先处理块1从右往左i3nxt[3]5不在块1内所以out[3]5cnt[3]1i2nxt[2]3在块1内所以out[2]out[3]5cnt[2]cnt[3]12i1nxt[1]2在块1内所以out[1]out[2]5cnt[1]cnt[2]13。块2i6nxt[6]8不在块2内out[6]8cnt[6]1i5nxt[5]6在块2内out[5]out[6]8cnt[5]2i4nxt[4]8不在块2内out[4]8cnt[4]1。块3i7nxt[7]8out[7]8cnt[7]1。得到块内跳表位置outcnt153252351481582681781查询从1出发ans cnt[1] 3x变成out[1]5。5仍≤nans cnt[5]2x变成out[5]8。xn1停止答案5。手动模拟一遍确实是1→2→3→5→6→出界正好5次。查询从3出发ans cnt[3]1x5ans cnt[5]2x8停止答案3。模拟路径是3→5→6→出界。可以明显看到分块就是把同一块内的连续几步压缩成一步代价仅仅是预处理时多花O(n)的时间。3.4 块大小怎么选如果你只需要输出所有起点的答案查询阶段总复杂度是O(n * n/S)预处理阶段是O(n)拆位阶段是O(nB)。所以总复杂度大概是阶段复杂度拆位求nxtO(nB)分块预处理O(n)全部查询O(n² / S)合计O(nB n² / S n)要让n²/S和nB平衡取S√n是比较稳的选择。实际实现时我习惯写成int S sqrt(n) 1;因为整数开根后向下取整可能导致S偏小多1个能避免一些边界问题。如果n是1e5B30√n≈317n²/S≈3.15e7再乘上常数现代机器上是可以轻松跑完的。如果你发现总时间偏紧可以把S调大到400~500减少查询次数但要小心块内转移链变长预处理耗时反而可能增加。这类题的常数问题最好的办法就是拿不同S去实测。4. 完整代码实现下面这份代码可以直接复制使用。用的是1-indexed比较贴近题目习惯。这里我统一默认数组元素范围在1e9以内所以位宽B30但如果输入可能出现2^30以上的数记得调大B。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } const int B 30; // 根据 a[i] 上限调整 vectorint nxt(n 1, n 1); vectorint last(B, n 1); // n1 表示“右侧不存在该位为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; // 块数 vectorint blockId(n 1); for (int i 1; i n; i) { blockId[i] (i - 1) / S 1; } vectorint 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]第一次跳出当前块后的落点n1表示出界 // cnt[i]跳出当前块所需的跳跃次数 vectorint 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; // 可能是另一块中的位置也可能是n1 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; }几个实现细节再强调一下n1这个哨兵值贯穿全程代表“跳出数组”。所以last初始化为n1nxt初始化为n1out也会落到n1更新last时直接赋值而不是取min因为倒序扫描保证了新位置的下标一定更小在判断nxt[i]是否和i在同一块时必须先判to n否则blockId[n1]越界查询循环里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]n1时cnt[i]1out[i]n1。这样所有情况都有统一的转移方程不会串味。5.4 位宽设置不当导致漏算如果输入数据有大于2^30的数B30会漏掉高位。建议看题目的数据范围如果a[i]可以是int的全部范围B至少设31如果开了long longB最好设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]要么是更大的下标要么是n1。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从右往左转移”这两个关键点彻底想明白以后再遇到类似题你会顺畅很多。我就是这样从“题解看得懂”变成“下次能自己写出来”的。