Bakas Trick

Trick 名何意味。

又名：不删除双指针。

常用于数区间，区间信息通常带有可合并的特质，也就是通常可以用线段树维护，如区间加，区间上的动态 DP（矩阵乘法）。

实现方法是：定义双指针 $L,R$ 与辅助变量 $\mathrm{mid}$，每次向右移动指针 $R$，维护 $[[L,\mathrm{mid}],\mathrm{mid}]$ 与 $((\mathrm{mid},R],R]$ 的信息（后者使用变量维护即可）。然后利用前面的信息把指针 $L$ 右移直到 $[L,\mathrm{mid}]+(\mathrm{mid},R]$ 合法（$+$ 是任意区间合并运算）。若 $L>\mathrm{mid}$ 仍不合法，则令 $\mathrm{mid}\leftarrow R,L\leftarrow R$，从后往前重新建立 $[[L,\mathrm{mid}],\mathrm{mid}]$ 的信息。

可以证明，每个数被 $L,R$ 各从前往后扫一次，被 $L$ 从后往前扫一次，时间复杂度 $O(n)$ 且码量略小于线段树。

1. P10144 [WC2024] 水镜

令 $L$ 为原题中的 $2L$（本质相同），设 $f_{l,r,0/1}$ 表示在区间 $[l,r]$ 中，取 $h_r/L-h_r$，合法的 $L$ 的取值范围，可以感受到 $L$ 是一段连续的区间。

有转移：$f_{l,r,0}\leftarrow f_{l,r,0}\cup (f_{l,r-1,1}\cap (-\mathrm{\infty },a_r+a_{r-1}))$，$f_{l,r,1}\leftarrow f_{l,r,1}\cup (f_{l,r-1,0}\cap (a_r+a_{r-1},+\mathrm{\infty }))$。

若 $a_{r-1}<a_r$，那么 $f_{l,r-1,0}$ 亦可 $\to f_{l,r,0}$，$a_{r-1}>a_r$ 同理。

合法的条件是 $f_{l,r,0}\cup f_{l,r,1}\ne \mathrm{\varnothing }$，可以发现若 $[l,r]$ 合法，则 $[l^{\prime },r^{\prime }]\subseteq [l,r]$ 均合法，因此对于每个 $r$ 找到最小的 $l$ 即可。

写成 $(\cup ,\cap )$ 矩乘的形式，Baka's Trick 维护区间乘法即可，注意运算顺序和对单位矩阵，空矩阵的处理。