浅谈一类倍增-CF1007C

spdarkle · 2023-12-09 15:48:50 · 个人记录

浅谈一类倍增。

众所周知，我们的常用倍增的实现是：先确定最大增量 p=2^{x}，其中 x=\lfloor\log N\rfloor，并确定初始答案 res=0。

不断检验 res+p 是否合法，若合法则 res\leftarrow res+p。然后 p\leftarrow \frac{p}{2}。

有另外的倍增写法，这是我初学倍增的想法：令当前答案 res=0 与倍增步长 x=1，有：

1. 检验 res+x 是否合法
2. 合法：res+x\to res',\min(N-res',2x)\to x。
3. 非法：x=\max(\lfloor\frac{x}{2}\rfloor,1)

在一维的情况下，容易发现它的次数最多是 3\log N。

涉及到一个平面问题呢？如答案是一个点 (a,b)，check 仅能知道当前答案 (res_x,res_y) 中 [res_x<a],[res_y<b],[res_x>a]|[res_y>b] 三个限制为真的其中一个，则普通倍增是无法扩展的。

但有幸，第二种倍增下，两个维度是独立的，可以分别维护两个维度的答案和步长，有：

• [res_x<a]$ 为真，有 $res_x+a_x\to res_x',\min(N-res_x',2a_x)\to a_x'
• 否则将两个步长全部减半。

最多进行 8\log N 次，这是因为一个维度 3\log N，而两个维度重叠起来需要加上不必要的减半复杂度。

进而可以扩展到 T 维，复杂度 (T^2+2T)\log N 次。这是因为每一维度独立有 3T，同时会因为另外 T-1 个维度导致回跳 T-1 步，所以就是 T(T-1)+3T=T^2+2T。