倍增值域分块
stripe_python · · 算法·理论
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[题解]
将
考虑倍增值域分块。将
需要查询块内
:::::
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 > x ,则块内元素整体-x 。 - 若
B^{k+1} \le x ,则块内元素无变化。 - 若
x \in [B^k,B^{k+1}) ,则需要处理部分块内元素。
对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间
类似势能线段树地,维护当前内非零数字的个数,在
视
可以使用平衡树代替线段树,空间做到线性但时间常数过大。考虑对线段树底层分块,长度
取略大的
:::::
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_i \le k ,则0 \sim k-1 加上a_i 的数均可被表示,令k \gets k+a_i 。 - 若
a_i>k ,则k \sim a_i 必然无法表示,k 即为所求的\text{mex} 。
注意到
观察这个排序的目的,我们只要知道区间 kth 就能实现上面的过程了。故使用树状数组套动态开点权值线段树,支持单点修改,查询区间 kth 在
下面给出复杂度更优的做法。我们考虑倍增值域分块,将元素按
- 若
x \le k ,则k \gets k+x ,且x+2^i \ge 2^{i+1} ,故整块中所有数都对k 有贡献,令k 加上块内元素和。 - 若
x>k ,则k 即为所求。
这样一来,我们对每块开一棵线段树,支持单点修改,区间求和区间
::::::