SOJ1835 题解

题意

给出一个 \(1,\dots,n+1\) 的排列 \(v_{1},\dots,v_{n+1}\) 与两组权值 \(a_{1,\dots,n},b_{1,\dots,n}\)。满足 \(v_{n+1}=n+1\)。

构造一张 \(n+1\) 个点的有向图：

• 对于 \(i=1,\dots,n\)，从 \(i\) 向 \(i+1\) 连一条权值为 \(a_i\) 的边；
• 对于 \(i=1,\dots,n\)，找到最小的 \(i<j\le n+1\) 满足 \(v_j>v_i\)，从 \(i\) 向 \(j\) 连一条权值为 \(b_i\) 的边。

一条路径的权值为路径上边权的最大值。特别的，若一条路径不包含任何边，则其边权为 \(0\)。

有 \(q\) 次询问，每次询问给出 \(x,y\)（\(x\le y\)），求 \(x\) 到 \(y\) 的权值最小的路径的权值。

\(1\le n,q\le 5\times 10^5\)，\(1\le a_i,b_i\le 10^9\)。

题解

设 \(i\) 向 \(p_i\) 连权值为 \(b_i\) 的边。简单分析可知，一定不存在 \(i<j\wedge p_i<p_j\)。于是当 \(p_x\le y\) 时，路径一定会经过 \(p_x\)。

设 \(d_x\) 为 \(x\) 走到 \(p_x\) 的最小路径权值。一种走法是直接走 \(b_x\) 的边；另一种是先走到 \(x+1\)。因为 \(p_{x+1}\le p_x\)，接下来一定会走到 \(p_{x+1}\)，故权值对 \(d_{x+1}\) 取 \(\max\)，并走到 \(p_{x+1}\)，重复上述过程。显然最终一定会走到 \(p_x\)。这个过程可以用倍增优化做到一个 \(\log\)。

然后考虑询问。一种贪心方法是：若 \(p_x\le y\)，则权值对 \(d_x\) 取 \(\max\)，走到 \(p_x\)；否则权值对 \(a_x\) 取 \(\max\)，走到 \(x+1\)。

将所有询问离线，从左往右扫描线。设当前到 \(i\)，考虑所有 \(j<i\wedge p_j>i\) 的 \(j\)。将其排序，设为 \(j_1,\dots,j_k\)，并另将 \(i\) 设为 \(j_{k+1}\)。则从 \(x\) 出发，路径一定是先不断跳 \(p_x\) 跳到 \(j_l\)，再跳到 \(j_l+1\)，再不断跳 \(p\) 跳到 \(j_{l+1}\)。一直跳到 \(j_{k+1}\) 为止。发现是一段后缀 \(\max\)，可以用线段树维护每个 \(j\) 跳到下一个 \(j\) 的最小路径权值。因为扫描的时候 \(j\) 的更新类似栈，且每个 \(j\) 只会入栈出栈一次，故复杂度 \(O(n\log n)\)。

PS：其实 \(j\) 数组就是考虑到 \(i\) 时笛卡尔树上的右链。这样思考形象一些。