#14032: 作者提供的解法


xavier13540 (柊 四千)

School : 國立臺灣大學
ID : 21783
IP address : [111.240.170.74]
Last Login :
2021-09-01 09:14:26
c618. 快冷靜下來啊我自己! | From: [140.112.229.87] | Post Date : 2018-06-02 23:54

雖然是基礎題還是放一下題解好了 www

題目一開始就提供每個 $\color{black}{p_i}$ 了,所以沒必要依序計算 $\color{black}{q_2, q_3, \ldots, q_n}$。以下提供兩種方法在 $\color{black}{O(n)}$ 時間內算完 $\color{black}{q_i}$ 們:

方法一:倒著算 + list

建立一條 list 像這樣:
\[\color{black}{-\infty\rightleftarrows1\rightleftarrows2\rightleftarrows\ldots\rightleftarrows n\rightleftarrows\infty}\]
讓這個 list 在計算 $\color{black}{q_i}$ 時,裡面的元素除了 $\color{black}{\pm\infty}$ 以外,恰好就是 $\color{black}{p_1, \ldots, p_i}$。這樣一來,想算 $\color{black}{q_i}$,只要看 $\color{black}{p_i}$ 左右兩邊和 $\color{black}{p_i}$ 的距離就行了。算完 $\color{black}{q_i}$ 後,把 $\color{black}{p_i}$ 從這個 list 裡拔掉,就能在計算 $\color{black}{q_{i-1}}$ 時保持上述提到的良好性質。

方法二:按 $\color{black}{p_i}$ 遞增順序算 + stack

計算 $\color{black}{q_i}$ 需要「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j<p_i}$ 的最大 $\color{black}{p_j}$」以及「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」。我們維護一個 stack,保存 $\color{black}{(i, p_i)}$ 數對們,且在任意時候 stack 裡的元素都是遞增的 (這裡遞增是指滿足偏序關係 $\color{black}{\preceq}$)。這樣一來,「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j<p_i}$ 的最大 $\color{black}{p_j}$」們就能在 $\color{black}{O(n)}$ 時間內算完。另外,我們還需要「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」們,而這可以用同樣的方法再做一次得到。但其實在維護上述的 stack 時,一旦有元素被 pop 掉,我們就知道那個被 pop 掉的 $\color{black}{i}$ 的「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」是多少了,也就是可以只做一次單調 stack。

 
#14033: Re:作者提供的解法


asnewchien@gmail.com (david)

School : No School
ID : 68108
IP address : [61.223.61.40]
Last Login :
2021-09-24 13:01:45
c618. 快冷靜下來啊我自己! | From: [1.168.30.127] | Post Date : 2018-06-03 10:15

雖然是基礎題還是放一下題解好了 www

題目一開始就提供每個 $\color{black}{p_i}$ 了,所以沒必要依序計算 $\color{black}{q_2, q_3, \ldots, q_n}$。以下提供兩種方法在 $\color{black}{O(n)}$ 時間內算完 $\color{black}{q_i}$ 們:

方法一:倒著算 + list

建立一條 list 像這樣:
\[\color{black}{-\infty\rightleftarrows1\rightleftarrows2\rightleftarrows\ldots\rightleftarrows n\rightleftarrows\infty}\]
讓這個 list 在計算 $\color{black}{q_i}$ 時,裡面的元素除了 $\color{black}{\pm\infty}$ 以外,恰好就是 $\color{black}{p_1, \ldots, p_i}$。這樣一來,想算 $\color{black}{q_i}$,只要看 $\color{black}{p_i}$ 左右兩邊和 $\color{black}{p_i}$ 的距離就行了。算完 $\color{black}{q_i}$ 後,把 $\color{black}{p_i}$ 從這個 list 裡拔掉,就能在計算 $\color{black}{q_{i-1}}$ 時保持上述提到的良好性質。

方法二:按 $\color{black}{p_i}$ 遞增順序算 + stack

計算 $\color{black}{q_i}$ 需要「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j<p_i}$ 的最大 $\color{black}{p_j}$」以及「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」。我們維護一個 stack,保存 $\color{black}{(i, p_i)}$ 數對們,且在任意時候 stack 裡的元素都是遞增的 (這裡遞增是指滿足偏序關係 $\color{black}{\preceq}$)。這樣一來,「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j<p_i}$ 的最大 $\color{black}{p_j}$」們就能在 $\color{black}{O(n)}$ 時間內算完。另外,我們還需要「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」們,而這可以用同樣的方法再做一次得到。但其實在維護上述的 stack 時,一旦有元素被 pop 掉,我們就知道那個被 pop 掉的 $\color{black}{i}$ 的「滿足 $\color{black}{j < i}$ 且 $\color{black}{p_j>p_i}$ 的最小 $\color{black}{p_j}$」是多少了,也就是可以只做一次單調 stack。



題目裡的故事好精彩。

 
ZeroJudge Forum