神秘的单调栈
Dexterha
·
·
算法·理论
区间不包含问题
有 n 个二元组 (L_i,R_i)，其中 i,L_i,R_i\in[1..n]，对于每一个 x，你需要找到最大的 y，使得：\
特殊需求：**「在线」**
每给出一个二元组 $(L_x,R_x)$，你就需要回答一次 $y$。
特殊需求：**「时限」**
你的算法复杂度不高于 $\Theta(n)$。
## 解法
可以发现 $L_y>L_x\lor R_y<R_x$ 这两个条件独立，对于当前的 $x$，\
令 $y_1,y_2$ 最大且分别满足 $y_1<x\land L_{y_1}>L_x$ 与 $y_2<x\land R_{y_2}<R_x$，\
那么 $y=\max\left\{y_1,y_2\right\}$，所以只需要维护 $y_1$ 与 $y_2$ 即可，这里只讨论如何维护 $y_1$。
设 $\mathrm{pre}_i$ 表示 $x=i$ 时对应的 $y_1$，可以通过以下方式快速得到 $\mathrm{pre}_i$：
$$
\begin{aligned}
& \mathbf{for}\ i\ \mathbf{in}\ [1..n]\ \mathbf{do}\\
& \qquad \mathrm{pre}_i\leftarrow i-1 \\
& \qquad \mathbf{while}\ L_{\mathrm{pre}_i}\le L_i\ \mathbf{do} \\
& \qquad \qquad \mathrm{pre}_i\leftarrow\mathrm{pre}_{\mathrm{pre}_i} \\
& \qquad \mathbf{end}\ \mathbf{while} \\
& \mathbf{end}\ \mathbf{for}
\end{aligned}
$$
:::info[正确性证明]
~~这就是链式单调栈啊~~
考虑使用归纳法证明正确性。
假设 $\mathrm{pre}_{[1..x-1]}$ 都求对了，且正确的 $\mathrm{pre}_x$ 为 $c$。\
假设存在 $y\in(c..x)$ 满足 $\mathrm{pre}_y<c$：\
因为 $c$ 是正确的，那么有 $L_c>L_x,L_y\le L_x$，可以推出 $L_c>L_y$，这与 $\mathrm{pre}_y<c$ 矛盾，\
所以从 $x-1$ 开始，一直跳 $\mathrm{pre}$，在跳到 $c$ 左侧之前一定会跳到 $c$。
:::
:::info[复杂度证明]
~~这就是链式单调栈啊~~
考虑使用势能分析证明复杂度为 $\Theta(n)$。
设处理到 $\mathrm{pre}_i$ 时势能 $\phi$ 为从 $i$ 开始跳 $\mathrm{pre}$ 跳到 $0$ 的步数。
每处理一个 $\mathrm{pre}$ 会导致 $\phi\xleftarrow{+} 1$，每当条件 $L_{\mathrm{pre}_i}\le L_i$ 为真时，就会使 $\phi\xleftarrow{-} 1$，且对于每个 $i$，条件 $L_{\mathrm{pre}_i}\le L_i$ 只有一次为假。
这个代码的复杂度可以看成 $L_{\mathrm{pre}_i}\le L_i$ 的判定次数，由于 $\phi$ 的总增加次数为 $n$，所以总判定次数不超过 $2n$，那么总复杂度就是 $\Theta(n)$。
:::
## 改进
尝试以下伪代码：
$$
\begin{aligned}
& \mathbf{for}\ i\ \mathbf{in}\ [1..n]\ \mathbf{do}\\
& \qquad \mathrm{pre}_i\leftarrow i-1 \\
& \qquad \mathbf{while}\ L_{\mathrm{pre}_i}\le L_i\land R_{\mathrm{pre}_i}\ge R_i\ \mathbf{do} \\
& \qquad \qquad \mathrm{pre}_i\leftarrow\mathrm{pre}_{\mathrm{pre}_i} \\
& \qquad \mathbf{end}\ \mathbf{while} \\
& \mathbf{end}\ \mathbf{for}
\end{aligned}
$$
发现 $\mathrm{pre}_i$ 就变成了 $x=i$ 时的答案 $y$。
证明方式依然不改变。
## 推广
受此问题启发，对于更一般的问题，有函数 $f(a,b)\in[0..1]$ 满足：\
$f(a,b)=0\land f(b,c)=0 \Rightarrow f(a,c)=0$\
（等价于 $f(a,x)=1\land f(b,x)=0 \Rightarrow f(a,b)=1$，这两个条件可以从不同角度证明其正确性）
设 $\mathrm{pre}_{x}=\max\limits_{i\in[0..x)\land f(x,i)=1}{i}$，要求快速求 $\mathrm{pre}_x$。
同理给出伪代码：
$$
\begin{aligned}
& \mathbf{for}\ i\ \mathbf{in}\ [1..n]\ \mathbf{do}\\
& \qquad \mathrm{pre}_i\leftarrow i-1 \\
& \qquad \mathbf{while}\ f\left(\mathrm{pre}_i,i\right)=0\ \mathbf{do} \\
& \qquad \qquad \mathrm{pre}_i\leftarrow\mathrm{pre}_{\mathrm{pre}_i} \\
& \qquad \mathbf{end}\ \mathbf{while} \\
& \mathbf{end}\ \mathbf{for}
\end{aligned}
$$
也就是说单调栈其实并不要求条件成立具有传递性，那么这又有什么用呢？
## 例题：衡·水生木护
定义函数 $h(x,m)=\begin{cases}h(x-m,m) & m\le x \\ x & 0\le x < m \\ h(x+m,m) & x<0\end{cases}$，其中 $x,m\in\mathbb{R}\land m>0$。
现在，你有 $n$ 个波浪线 $g_{[1..n]}$，波浪线 $i$ 使用一个三元组 $(d_i,c_i,m_i)$ 表示，\
其中 $d_i,c_i,m_i\in \mathbb{Z}\land m_i>0$，其函数图像为：
$$
g_i(x)=d_i+\left| h(x+c_i,2m_i)-m_i \right|
$$
对于每一个 $x$，你需要找到最大的 $y$，使得：\
$y<x\land \exists z\in \mathbb{R},g_y(z)>g_x(z)
特殊需求：「在线」
每给出一个波浪线，你就需要回答一次 y。
特殊需求：「时限」
你的算法复杂度不高于 \Theta(n\log w)，其中 w 为值域大小。
:::::success[题解]
注：这是原创题，题解可能有误，欢迎大家指正
令 f(a,b)=\left[\exists z\in \mathbb{R},g_a(z)>g_b(z)\right]，那么 f(a,b)=0\Rightarrow \forall z\in \mathbb{R},g_a(z)\le g_b(z)，这个条件具有传递性，然后直接直接套用推广中的结论即可。
::::info[以防你不知道如何快速求 f]
\exists z\in \mathbb{R},g_y(z)>g_x(z)$ 等价于 $\exists z\in \mathbb{R},g_x(z)-g_y(z)<0
由于函数特殊，这个命题等价于 \exists z\in \mathbb{Z},g_x(z)-g_y(z)<0，之后的步骤都将函数 h 看作取模，z 看成整数。
现在，只需要求出 \min\left\{g_x(z)-g_y(z)\right\} 即可。
\
（蓝色、绿色为两个形如 y=k\cdot h(x+a,m)+b 的函数）
波浪函数没有什么好的性质，所以考虑拆绝对值：
g_i(x)=d+\left| h(x+c,2m)-m \right|=\max\left\{ h(x+c,2m)-m+d,m- h(x+c,2m)+d\right\}
\
（紫色为波浪函数）
但是这依然不够用，考虑另一种拆法：
g_i(x)=d+\left| h(x+c,2m)-m \right|=\min\left\{ h(x+m+c,2m)+d,2m-h(x+m+c,2m)+d\right\}
\
（紫色为波浪函数）
对 g_x 使用第二种拆法，对 g_y 使用第一种拆法，然后就可以将求 \min\left\{g_x(z)-g_y(z)\right\} 拆解成四个子问题。
每个子问题形如对变量 x 求：
\min\left\{ k_1\cdot h(x+a_1,m_1) + k_2\cdot h(x+a_2,m_2) \right\}+b
其中 k_1,k_2\in \{-1,1\}。
令 p(x)=k_1\cdot h(x+a_1,m_1) + k_2\cdot h(x+a_2,m_2)
考虑 x\xleftarrow{\pm} 1 对 p 取值的影响，容易发现一个结论，p 取到极值的时候，一定有：
h(x+a_1,m_1)=0\lor h(x+a_1-1,m_1)+1=m_1\lor h(x+a_2,m_2)=0\lor h(x+a_2-1,m_2)+1=m_2
（注意，这里的 x 仍然是整数）
根据 k_1,k_2 的取值，实际上只需要考虑这四个条件中的两个为真的情况。
枚举为真的那个条件，你可以得到这样的限制：
x\equiv \alpha_1 \pmod {\beta_1}
根据常见转化，可以得到：
x=t\beta_1+\alpha_1
现在就是在求 \min\left\{\left(\left(t\beta_1+\alpha_1\right)+\alpha_2 \right)\bmod \beta_2\right\}，其中 t 为变量。
焰烬曙明，终于遇到可以求的式子了，带回问题即可。
:::info[以防你不会求 \min\left\{(ax+b)\bmod c\right\}]
既然你都读到这里了，应该不至于
现在，让我们忘掉之前定义的所有东西。
需要对一个变量 x 求 \min\left\{(ax+b)\bmod c\right\}
那么就是对两个变量 x,y 求：\
在满足 ax+cy+b\ge 0 的情况下 ax+cy+b 的最小值。
你回忆起裴蜀定理，所以最小值为 b\bmod \gcd(a,c)。
:::
::::
:::::
后记
偶然发现单调栈除了维护“所有元素中任意一个数左和右两边距离最近的首个比该数大或小的位置在哪”，还可以干一些特别的事。
也算是 「广义单调栈」 吧，但是毕竟终究还是单调栈，摆脱不了简单算法的命运。
:::info[关于例题]
你可能发现，这个例题最难的部分不在这个结论，
我实在想不到什么好的 f 可以满足这个性质又不容易被其它算法替代，
然后就出了这样一个买椟还珠、本末倒置的题，这就是为了一碟醋包了一盘饺子吧。
:::