## ZJ i531 - 拿竿拿來 題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 離線 ?

首先，$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',R')$，現在要求的這筆查詢叫做$(L,R)$，分成以下幾種情形 :

1.如果 $L$ 所在的區間和 $R$ 一樣，那可以直接暴力做，因為暴力做的複雜度其實不會超過 $O(\frac{N}{\sqrt{Q}})$ 。

2.否則，如果 $L$ 所在的區間和 $L'$ 一樣，在一開始先把左指標移動到區間的最右邊，開始往左移動，而 $R$ 因為保持遞增，所以照正常的擴大就好。

3.最後是 $L$ 所在的區間和 $L'$ 不同，就移到下個區塊，把之前的全部刪掉從頭開始。

### 結論

我們可以發現不管哪一種 $\text{case}$ 最多指標只會移動 $O(\frac{N}{\sqrt{Q}})$ 次，最後此問題可在 $O(N\sqrt{Q})$ 內解決。