ZJ i531 - 拿竿拿來 題解

<<回主頁

離線 ?

首先，

$O(NQ)$肯定是可以算出答案的，但以這題的測資範圍顯然不夠快，雖然是區間查詢，但這裡也很難用線段樹之類的結構維護，因此會想離線看看。

普通的莫隊 (Mo's algo) ?

莫隊算法是一種離線演算法，把區間分成

$\sqrt{Q}$ 個，可以以

$O(w\cdot N\sqrt{Q})$ 的時間複雜度算出，

$O(w)$是左右指標移動一格的複雜度。

將

$O(w)$ 做到

$O(1)$

用普通的莫隊維護其實發現有點難把

$O(w)$ 做到

$O(1)$，區間擴大沒啥問題，但區間變小的話很難做到

$O(1)$ 。

這時我們可以用「回滾莫隊」!

分成幾種情形，假設上一筆已經做好的查詢叫做

$(L^{\prime },R^{\prime })$，現在要求的這筆查詢叫做

$(L,R)$，分成以下幾種情形 :

1.如果

$L$ 所在的區間和

$R$ 一樣，那可以直接暴力做，因為暴力做的複雜度其實不會超過

$O(\frac{N}{\sqrt{Q}})$ 。

2.否則，如果

$L$ 所在的區間和

$L^{\prime }$ 一樣，在一開始先把左指標移動到區間的最右邊，開始往左移動，而

$R$ 因為保持遞增，所以照正常的擴大就好。

3.最後是

$L$ 所在的區間和

$L^{\prime }$ 不同，就移到下個區塊，把之前的全部刪掉從頭開始。

結論

我們可以發現不管哪一種

$\text{case}$ 最多指標只會移動

$O(\frac{N}{\sqrt{Q}})$ 次，最後此問題可在

$O(N\sqrt{Q})$ 內解決。