倍增分块小记

· · 算法·理论

这种东西真该好好总结了。若无特殊说明，q 为询问和操作次数，V 为值域。

本文同步发布至博客园。

值域倍增分块

比较常见的一种，一般是将 \le/\ge 多少的数 +/- 多少。加减不应混合，否则没有变化的单调性。

核心思想是按 [B^k,B^{k+1}) 分块。观察一些变化的优秀性质，每个块用一个数据结构维护这个块内的数，遇到特殊情况（如要跳出当前块或不满足了某种限制）时直接暴力，其余用数据结构维护。

其实有点像势能线段树，暴力而优雅，势能通常是到跳出当前块的距离。

尤其需要注意：某个数在一个块内会暴力多少次？能保证在一个优秀的次数（例如 O(B) 次）后跳出去吗？

P4587 [FJOI2016] 神秘数

我们用 f(S) 表示 S 的神秘数。

我们维护这样的过程：维护一个变量 A，表示 [0,A] 的数都能表示，A + 1 则不行。每次取出 S 中的最小元素 x 随后删除，考虑 x 的影响：

最后 A + 1 就是 f(S)，在此基础上，我们考虑对值域倍增分块，我们从左往右枚举块。对于块 [2^k,2^{k+1})，令在其中的最小值为 x：

离线下来扫每一个块 ST 表做一遍就行了。最初见到的倍增分块是一道模考题，与此题并无区别。

P7447 [Ynoi2007] rgxsxrs

我们有一个很暴力的做法，维护一棵线段树，修改时根据当前节点的最大值来更新：

但这太容易被卡爆了，极小极大交替放状物就死了。

考虑倍增分块，以 B 为基数， [B^k,B^{k+1}) 为一块，每个块用一棵线段树维护。修改时，考虑现在节点的最小值 L 和最大值 R:

最后递归到叶子直接暴力修改即可，如果掉出去了就把它重新丢进它新到的块的线段树里。算算这个势能线段树的时间复杂度。假设 x \in [B^k,B^{k+1})，考虑每个块 i：

算上线段树本身的 \log，n,q 同阶，总时间复杂度 O(nB\log_BV\log n)。空间复杂度 O(n \log_B V)

但是这题还卡空间，注意到线段树的叶子节点最多最占空间，那么底层分块，设定阈值 K，线段树节点只存储长度 > K 的区间信息，长度 \le K 的直接暴力修改和查询。调整这个拍平的长度 K，可以做到空间复杂度 O(n)。实测 B = K = 32 时较优。

CF702F T-Shirts

典题了。

把 T 恤排序，人离线下来批量处理。相当于每次把 T 恤从左往右扫，将 >c_i 的人的钱数 b 减少 c_i，然后答案加 1。用上一题的方法即可。当然也可以用平衡树，偏题不介绍了。

P8522 [IOI 2021] 地牢游戏

倍增分块，考虑根据能力值 z 在块中的变化，若 z \in [B^k,B^{k+1})，容易发现对于 s_i < B^k 的地牢，一定胜；对于 s_i \ge B^{k+1}，一定败。注意与 z 同块的地牢不确定。

那么我们有一个 navie 的想法。看到在地牢间一直跳跃，想到倍增。设 f_{k,x,i} 表示 z \in [B^k,B^{k+1}) 时从 i 开始跳，跳 2^x 步后到的地牢。同理设 s_{k,x,i}，但是表示这个过程中能力值会增加的量。

我们每次倍增，只要没跳出当前块或者经过了同块的地牢（因为你可能胜也可能败，不像其他地牢胜负是确定的），就一直跳。无法倍增时就直接停下暴力，看现在能否打败当前的地牢，下一次继续倍增。

乍一看感觉 z 在同一个块时最多停下 B 次，共有 \log_B V 个块，算上倍增，感觉是对的。但其实当你面对同块的地牢时，如果胜了，那至少加 B^k，时间复杂度是对的。而一旦输了，你只能加 l_i，而 l_i 可以远小于 s_i 甚至等于 1，于是你只能在这个块里缓慢地蠕动，可能停下不止 B 次，爆炸了。

所以很烦人的是输。那我们考虑将这些输也丢进倍增里。f_{k,x,i},s_{k,x,i} 定义不变，但我们只认为 s_i < B^k 赢，其余情况钦定全输。

此时就又有问题了，怎么保证经过的所有同块的地牢，英雄全输？考虑反着求 z \ge 多少时就会有原本钦定败的地牢反而赢了，这个阈值设为 g_{k,x,i}。

查询时直接倍增跳，只要 $z$ 没有 $\ge$ 阈值就跳。否则就停下来根据现在的地牢看胜负就行，然后继续跳。我们只会停下来 $B\log_B$ 次，每次倍增 $\log V$，加上预处理，总共 $O(qB\log_B V \log V + n\log_BV\log V)$。 具体实现上，$V=10^7$，但是能力值可能 $>V$，我们在原本的最后一个块 $[B^k,B^{k+1})$ 后再追加一个块 $[B^{k+1},+\infty)$，这样可以省掉一些细节。 调一下 $B$ 让预处理和查询复杂度平衡即可。 ## 序列倍增分块 这个不怎么常用。它将序列倍增分块，一般取 $[2^k,2^{k+1})$ 为一块。注意块长的特殊性。 :::warning[致歉] 这种我只找到两道，最后一道前面的思维 & 算法链较长，可能不太适合倍增分块练手。但是我真找不到了，有没有超级大蛇推荐 /kel。 ::: ### [P11398 众数](https://www.luogu.com.cn/problem/P11398) 观察到 $\sum k \le 5\times10^7$，显然每次肯定只能从后往前枚举，需要快速查前缀众数。 众数除了根号分治就是分块，此题考虑分块。维护 $c_{i,x}$ 表示前 $i$ 个块 $x$ 的出现次数，$m_i$ 表示前 $i$ 个块的众数。单点修改直接更新 $c_{i,x},m_i$ 即可。 每次查询前缀众数，就是将前几个块的众数和散块的数合并计算，时间复杂度 $O((n+q+\sum k)\sqrt{n})$，这个都会。 但你发现查的位置是连续的，从后往前枚举块，那你可以用 $O(\sqrt{n})$ 的时间一并求出一个块内所有的前缀众数，如果有位置满足直接退出。但是如果答案位置在一个块的最右边，那你会多枚举 $\sqrt{n}$，所以总的时间复杂度是 $O((n+q)\sqrt{n}+\sum(k+\sqrt{n}))$，还是不太能通过。 能不能有种分块方法，从后往前分块，使得答案的 $k$（即倒数第 $k$ 的下标）所在的块长是 $O(k)$ 而不是 $O(\sqrt{n})$？这样每次最多多枚举 $O(k)$。 那考虑倍增分块，有一个结论： > $i$ 在的块的长度一定 $\le i$，是 $O(i)$ 级别。证明：若 $i \in [2^k,2^{k+1})$，则块长 $2^k$，显然 $2^k \le i$。 正好满足要求，于是从后往前倍增分块，修改查询与原本的根号分块差不多，时间复杂度 $O((n+q)\log n + \sum k)$。 ### [P14638 [NOIP2025] 序列询问](https://www.luogu.com.cn/problem/P14638) 观察到特殊性质 DE 比较特殊，从这个入手。记 $s_i=\sum\limits_{j=1}^{i} a_j$。 首先是 D 性质，因为 $L > \frac{n}{2}$，所以 $2L > n \ge R$，那你发现对于 $i$，某一个合法区间 $[a,b]$ 包含它，则 $i$ 到某一端点（$a$ 或 $b$）的距离一定 $\le L$，且这个端点有且只有一个。这个显然。 设 $f_i$ 表示以 $i$ 为左端点的所有合法区间中，价值的最大值。同理设 $g_i$ 但是是以 $i$ 为右端点。$f_i,g_i$ 是 simple 的，显然可以对 $s$ 建 ST 表，单次查询 $O(n)$ 时间求出。求解 $k_i$ 时，考虑离 $i$ 距离 $\le L$ 的是左端点还是右端点。左端点的答案为 $\max\limits_{1 \le j \le i - L + 1}f_j$，右端点为 $\max\limits_{i+L-1 \le j \le n} g_j$，$k_i$ 两者取 $\max$。采用单调队列能使单次询问做到线性。这个做法暂时还不知道有什么用。 其次是 E，此时合法区间一定跨过了序列中点，启示我们分治。设现在分治 $[l,r]$，取中点 $mid$，不妨先考虑左边。考虑左边部分的 $i$，设 $F_i$ 为以 $i$ 为左端点，右端点强制跨到右边（即 $>mid$）的所有合法区间中的最大价值，这个也能类似 $f_i$ 求出。那显然，因为我们钦定合法区间跨到右边，对于所有的 $l \le i < mid$，若这些区间包含 $i$ 则一定包含 $i+1$。所以对 $k_i$ 的贡献就是 $\max\limits_{j=l}^{i} F_j$。同理右边部分也可以类似求出。 所以可以对于每次询问都做一次分治，查询单次 $O(n \log n)$，总共 $O(nq\log n)$。还要优化。 接下来发扬人类智慧，考虑对 $L,R$ 倍增分块。分成 $O(\log n)$ 个块，第 $i$ 个块管辖 $[2^i,2^{i+1})$（说白话就是 $L=2^i,R=2^{i+1}-1$ 时的 $k$ 序列）。对于所有块做分治求出这个块的答案，时间复杂度 $O(n \log^2 n)$。 查询 $L,R$ 时，分为散块和整块。整块合并出的答案可以预处理，具体地，求出 $K_{i,j}$ 代表 $[i,j]$ 中的块合并出的 $k$ 序列，$O(n \log^2n)$ 预处理。对于散块，拆成了形如 $O(1)$ 次查询 $L',R'$，且满足 $L',R'$ 在同一块内（即 $2^t \le L' \le R' < 2^{t+1}$）。注意到此时 $2L' > R'$，故可以采用 D 性质的做法，求出散块的贡献。 如此，时间复杂度 $O(n \log^2 n + nq)$。