倍增值域分块

带 $\log$ 时间复杂度的均摊，可以分出两种常见的类型：

每个数被操作一次之后就会减半。
每个数被操作一次之后可能减小的很少，操作很多次后减半。

对于第一种问题，难点在于如何高效找到每次操作，有哪些数需要被减半。

对于第二种问题，常见的解决方法是倍增值域分块。

如果有问题可以归约到 $d\ge x$ 就 $d\gets d-x$ ，那还是很适合倍增值域分块的。

具体套路从题中来：

CF702F T-Shirts

有 $n$ 种 T 恤，每种有价格 $c_i$ 和品质 $q_i$ 。

有 $m$ 个人要买 T 恤，第 $i$ 个人有 $v_i$ 元，每人每次都会买一件能买得起的 $q_i$ 最大的 T 恤。一个人只能买一种 T 恤一件，所有人之间都是独立的。

问最后每个人买了多少件 T 恤？如果有多个 $q_i$ 最大的 T 恤，会从价格低的开始买。

$n,m\le 2\times 10^5$

将物品按照 $q_i$ 从大到小排序，相当于物品卖给所有能卖给的人。

考虑把人分成三等，第一种是穷光蛋， $v_j<c_i$ ；第二种是买完变成穷光蛋， $v_j\in[c_i,2c_i)$ ，第三种是富哥， $v_j\ge2c_i$ 。

你发现富哥买完了值域和穷光蛋没有相交，所以可以直接在平衡树上区间减。

而买完变成穷光蛋的人值至少会减半，所以暴力插回去就好。

平衡树维护， $\Theta(n\log^2 n)$ 。

P7447 [Ynoi2007] rgxsxrs

区间把 $>x$ 的元素减去 $x$ ，区间求和求 $\max$ 求 $\min$ 。

$n,q\le5\times 10^5,6\rm \ seconds,64\ MB$ 。

按照上题思路树套树基本很难搞了，因为区间操作不好合并标记。

我们来介绍一种很厉害的 倍增值域分块：

将值域按照 $[2^k,2^{k+1})$ 分为 $\mathcal O(\log V)$ 块。
每块用一棵下标线段树来维护该块的所有元素。

则我们知道了一件事，若将 $>x$ 的元素减去 $x$ ，则三种情况分别是（以下默认在 $[l,r]$ 拆成的区间内）：

若 $x<2^k$ ，则该块所有元素都需要减去 $x$ ，此时我们维护区间最小值，若最小值会掉落，则每次将最小值二分出来扔到某个块，其它元素打一个区间减。
若 $x\in[2^k,2^{k+1})$ ，则该块最大的几个元素需要减去 $x$ ，此时我们维护区间最大值，若最大值会掉落则二分出来扔到下面的某个块。
若 $x\ge 2^{k+1}$ ，则该块所有元素都不需要减去 $x$ ，此时什么也不用干。

复杂度分析就是每个元素如果要掉落就需要 $\cal O(\log n)$ 的时间，最多掉落 $\cal O(\log V)$ 次，故总复杂度 $\mathcal O((n+q)\log n\log V)$ 。

然后你就发现空间复杂度是优秀的 $\cal O(n\log n)$ ，过不了一点。

这个时候就要上 $\rm lxl$ 的神级技巧了，你可以底层按 $\log V$ 分块，这样每棵线段树只有 $\frac n{\log V}$ 个节点，还不影响复杂度，并且缓存很友好。

然后你再把 $\log V$ 棵树变成一棵树，每个节点维护 $\mathcal O(\log V)$ 的信息。

然后我就写这个破题写了一下午加一晚上……

注意第一版代码一定要写成易于理解的方式。

其实把值域分块换成 $[p^k,p^{k+1})$ 也是可以的，只需要把操作写成线段树搜索加剪枝的形式就可以了。

且这样好写好调，不要在主函数里写个 while 那种东西。

P9069 [Ynoi Easy Round 2022] 堕天作战 TEST_98

区间将 $\ne x$ 的数减去 $x$ ，求区间和。

$n,q\le 5\times 10^5,\rm 6\ seconds$ 。

把上面哪题代码改改就能用了。

需要特别注意的是，倍增分块的倍增底数理论上是 $e$ 最优，但实际操作往往 $16\sim 20$ 最优，建议考场上写一份通用底数的再慢慢卡。

CF1515I Phoenix and Diamonds

$n$ 种钻石，一颗第 $i$ 种钻石重量为 $w_i$ ，价值为 $v_i$ ，一开始第 $i$ 种钻石的库存为 $a_i$ 。接下来进行 $m$ 次操作：

1 k d：进货了 $k$ 个种类为 $d$ 的钻石；

2 k d：卖出了 $k$ 个种类为 $d$ 的钻石；

3 c：如果你有一个大小为 $c$ 的袋子，且按照第一关键字为价值（从大到小），第二关键字为重量（从小到大）的顺序取钻石的话，你最终可以取到钻石的价值为多少（注意操作不会真正执行）

$1\leq n\leq 2\times 10^5$ ， $1\leq m\leq 10^5$ ， $1\leq k,d,a_i\leq 10^5$ ， $1\leq c\leq 10^{18},\rm 5\ seconds$ 。

相当于动态维护买 T 恤。

第一第二种操作很明显不像线段树分治状物，那就只能线段树单点修改了，我们维护一个优先级从高到低的序列。

然后看 $3$ 操作，很明显复杂度要带 $\log c$ ，考虑如何让 $c$ 减半。

假设 $c\in[2^k,2^{k+1})$ ，或者说 $c$ 的最高位是 $k$ 。

把钻石分为 $\ge2^k$ 的和 $<2^k$ 的，考虑大钻石只能取一个。

我们无非就是从 $1$ 开始往后看到底跑多远嘛。

由于 $\ge 2^k$ 的只能有一个，我们维护每个大钻石和前面的小钻石的和 $f_i$ ，也就是说我们要找到出现最早的 $i$ 满足 $f_i\le c$ 。

$c$ 已经减半，接下来就可以递归了。

还有一种情况，是一直选小钻石，直到选到一个小钻石选不动了，这种情况下也会减半，我们设 $g_i$ 为该位置以及前面的小钻石的和，则我们要找到出现最晚的 $i$ 满足 $g_i\le c$ 。

我们动态维护 $c$ 的最高位，维护 $\log c$ 棵线段树即可。

但是这并不是很好写，因为你每次的在线段树上查东西是有一个初始下标（即上次选完的下标）的。

不如整体维护一棵线段树，进行一个贪心，你发现终止条件只需要写能取所有 $\le 2^{k+1}$ 的钻石时直接退出，以及不能取最小的（ $\ge 2^k$ 的钻石加上该区间内前面所有的 $<2^k$ 的钻石）却能取该区间内所有的 $<2^k$ 的钻石时取完退出。

如果都不成立，就先递归左子树花钱，再递归右子树花钱。

是不是感觉这个剪枝莫名其妙的？

但你只需要考虑最终我们的答案在线段树上拆出的 $\log n$ 段区间，假如我们最终方案中取了一个重钻石，那么跑到其他的地方都只会朴素的剪枝剪掉了，而会一直向这个重钻石递归，所以每位的时间复杂度都是 $\log n+\log n=\cal O(\log n)$ ，单次操作总复杂度 $\mathcal O(\log n\log V)$ 。

这个写法的实现极为简单。

P4587 [FJOI2016] 神秘数

给定序列， $q$ 次询问最小的不能被 $[l,r]$ 元素的子集和表示的正整数是多少。

$n,q\le 10^5$ 。

维护一棵主席树，首先我们可以把所有的 $1$ 收入囊中，然后你发现每次令 $\rm ans\gets \sum[1,ans]$ 就可以凑出能凑出的最大能表示的正整数，道理很显然。

然后你发现每有两次新收获时， $\rm ans$ 至少翻倍，这是因为第一次收获必定让 $\rm ans$ 变大，所以第二次收获的增加量一定来自最初的 $\rm ans$ 右边，所以暴力做就是对的。