倍增值域分块

· · 算法·理论

CF1098D Eels

定义多重集 S 的权值为:每轮操作选出 a,b \in S 满足 a \le b,若 2a \ge b 则获得 1 的得分,然后删去 a,b 并插入 a+b,直到 |S| \le 1 的最大得分。

维护多重集 S,进行 q 次操作,插入某个数或删除某个数,然后输出 S 的权值。

:::::success[题解]

将 S 升序排序为序列 a_1 \sim a_n。若 2 \sum\limits_{i=1}^{k-1} a_i \ge a_k 则称 a_k 是关键点,我们声称,答案恰为关键点的数目。

考虑倍增值域分块。将 [2^k,2^{k+1}) 中的数分到一块,则非关键点只能是每块的首个元素。直接扫过所有块,用总数减非关键点数即得答案。

需要查询块内 \min 与总和,用 multiset 维护,复杂度 O(q \log V)。代码。

:::::

P7447 [Ynoi2007] rgxsxrs

维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 l,r,x,对 i \in [l,r] 若 a_i>x 则令 a_i \gets a_i -x。
  • 给定 l,r,同时求出 [l,r] 的和,最小值,最大值。

强制在线。

:::::success[题解]

我们使用倍增值域分块,将 [B^k,B^{k+1}) 中的数分到一块,得到 \log_B V 块。修改时:

对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间 \max 和区间 \min。考虑三种块怎么修改:

类似势能线段树地,维护当前内非零数字的个数,在 \text{max} \le x 或区间为空时剪枝。注意到跌落只会执行 \log_b V 次,均摊复杂度是对的。

视 n,q 同阶,复杂度可以分析到 O\left(n\dfrac{B}{\log B} \log n\log V\right),空间 O(n \log_B V)。实现。

可以使用平衡树代替线段树,空间做到线性但时间常数过大。考虑对线段树底层分块,长度 \le \log n 的节点直接暴力,时间不变的情况下空间优化到线性。

取略大的 B 以平衡时空常数,微调底层分块的阈值后可以通过。我的实现取 B=14,对底层按 16 分块可稳定通过。代码。

:::::

QOJ9708 Yuuki and a problem

维护长为 n 的数组 a_i,支持 q 次操作:

  • 给定 i,v,令 a_i \gets v。
  • 给定 l,r,查询 [l,r] 子集和的 \text{mex},即最小的正整数 k 使得 \nexists S \subseteq [l,r] ,\sum \limits_{i \in S} a_i =k。

::::::success[题解]

考虑单次询问的做法。我们将 a_l \sim a_r 升序排序,维护 k 表示 0 \sim k-1 均能被子集和表示,按排序后的顺序扫描 a_i。

注意到 k \gets k+a_i 每做两次,k 的范围至少翻倍,故暴力扩展 k 的复杂度是 O(\log V) 的。

观察这个排序的目的,我们只要知道区间 kth 就能实现上面的过程了。故使用树状数组套动态开点权值线段树,支持单点修改,查询区间 kth 在 O(\log n) 棵树上二分。复杂度 O(q \log^2 n\log V) 难以通过,代码。

下面给出复杂度更优的做法。我们考虑倍增值域分块,将元素按 [2^i,2^{i+1}) 进行值域分组。设某块中最小元素为 x:

这样一来,我们对每块开一棵线段树,支持单点修改,区间求和区间 \min 即可。复杂度 O(q \log n\log V)。代码。

::::::