雜題瞎寫

來點(diǎn)亂搞題。

燈塔

首先，這是一個(gè) DP。
觀察到 \(\sqrt{|i - j|}\) 的取值范圍是 \(O(\sqrt n)\) 的。
所以枚舉每個(gè)取值，轉(zhuǎn)移就是區(qū)間 \(\max\)。
隨便寫寫 \(O(n \sqrt n)\)。

當(dāng)然，這復(fù)雜度太高了，看著不舒服。
我們考慮刪除一些無用的狀態(tài)。
考慮若目前的最大值為 \(val\)，由于 \(\sqrt{|i - j|}\) 的取值不超過 \(\sqrt n\)，所以 \(<val - \sqrt n\) 的位置直接扔。
若目前的值相同且 \(\sqrt{|i - j|}\) 的值相同，則只有最遠(yuǎn)的有貢獻(xiàn)。
所以如果把有用的值從大到小排序，每次要么是 \(val - 1\) 要么是 \(\sqrt{|i - j|} - 1\)。
所以任意時(shí)刻有用的點(diǎn)不超過 \(O(\sqrt n)\)。

理論上講，由于每個(gè)點(diǎn)的值需要更新 \(O(\sqrt n)\) 次，在這里我們就可以草率的下結(jié)論說這題 \(O(n)\) 了。
但實(shí)際情況好像不是這樣。
因?yàn)槲覀冎皇潜ＷC了每個(gè)時(shí)刻 \(O(\sqrt n)\)。
考慮每個(gè)數(shù)保留 \(O(\sqrt n)\) 個(gè)單位時(shí)間，在這段時(shí)間內(nèi)會(huì)貢獻(xiàn) \(O(n^{\frac{1}{4}})\) 次修改。
然后總復(fù)雜度就到 \(O(n^{\frac{5}{4}})\) 了。

當(dāng)然，這個(gè)復(fù)雜度也不大，很輕松就過了。

啥，正解決策單調(diào)性優(yōu)化 DP？
沒學(xué)過。過。

分散層疊算法

之前沒做，現(xiàn)在補(bǔ)上。

考慮把所有的數(shù)放在一起，標(biāo)好每個(gè)數(shù)屬于哪個(gè)塊，排序。
然后直接按 \(k\) 分塊，每個(gè)塊開個(gè)桶維護(hù)某個(gè)值在這個(gè)塊及以后的第一次出現(xiàn)的位置。
然后這個(gè)塊內(nèi)的就硬掃即可。
單次查詢復(fù)雜度 \(O(k + \log n)\)，和分散層疊一樣。
但是估計(jì)常數(shù)小了很多。

還是分塊好用啊。