Baka's Trick

· · 个人记录

又名不带删的双指针。

一般地，我们想要求出某种值满足某条件的最长区间，且其具有单调性。下面以 r 增大时 l 不降为例。

当插入、删除元素都很容易，我们可以考虑双指针：r 增大时移动 l 直至满足条件或 l > r。

若删除元素很麻烦且合并两坨很容易，我们可以考虑 Baka's Trick。

考虑维护三个指针：

再维护 \forall i \in [l, mid]，[i, mid] 的“值”，和 [mid + 1, r] 的“值”。

当 r 增大，我们移动 l 直至满足条件或 l > mid。

若 l > mid，令 mid \leftarrow r，l \leftarrow r + 1，然后向左移动 l 直至 [l, r] 的“值”不满足条件。

最终 l 只会移动 O(n) 次，则时间复杂度为 O(nk)，其中 k 为单次加入一个元素和合并两坨元素的时间复杂度。

差分一下转化为求 \gcd > 1 的最长区间，然后就是上面这个东西的板子题了。

时间复杂度为 O(n \log w)，其中 w 为值域 10^{18}。