# f999 : SCP - A 特訓班 參考解法

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

### 1.$O(N^3)$ 暴力
這題如題目所說可以用$O(N^2)$枚舉每個$(L,R)$，每次檢查$O(N)$，所以是$O(N^3)$，但這複雜度顯然不好。

### 2.暴力的優化:$O(N^2)$
如果我們對於每個$R$枚舉，一開始$L=R$，接著每次$L$減少$1$，可以看成我一直把左邊一個個元素加入，利用DSU加一個元素是$O(1)$，而判斷的依據是當union之後，應該目前集合大小要是$R-L+1$，這樣代表全部是連通的，我們可透過是否連通來判斷條件，但加$N$次是$O(N)$，而$N$個$R$需要枚舉，時間複雜度是$O(N^2)$，還是不符合題目想要的。

### 3.問題簡化
這題我們可以把$A$序列重新編碼變成$(1,2,...,N)$，問題變成以下:

(問題#)給你一個$1\sim N$的某種排列$P$，問你有幾個$(P_L,...,P_R)$在經過排序之後，會變成一個連續公差$1$的等差數列?不過注意是環。

但這個問題由於有環很麻煩，我們考慮以下問題:

(問題◇)給你一個$1\sim N$排列，請問有幾個$(P_L,...,P_R)$在經過排序後可以變成一個連續公差為1之序列?
註:其實這問題就是:https://neoj.sprout.tw/problem/788/

我們可以證明，如果問題◇可以解決，我們也可以解決問題#，也就是我們最終要的問題。

### 4.解決問題◇
這個問題◇可以進一步的簡化成:
對於所有$(L,R)$區間，詢問符合$max(P_{L\sim R})-min(P_{L\sim r})=R-L$的數量。
這個問題可以透過分治的方式解決。

首先定義$F(L,R)$代表處理$L\sim R$區間，令$mid= \frac{L+R}{2}$，處理所有通過$mid$中點的區間，而其他的case則呼叫$F(L,mid)$與$F(mid+1,R)$，至於剩下要怎麼解決呢?

首先討論$(mid+1,R)$區間，當$R$增加的時候最大小值會單調，在上面放兩個指標(two pointers)。

而我們左邊從$mid$開始往左，有四個情況:

最大小值都在右邊:
$-L=max-min-R$

小在左大在右:
$min-L=max-R$

大在左小在右:
$-max-L=-min-R$

最大小值都在左邊:
$min-max-L=-R$

透過這些式子(其實只是移項)，可以快速得到，方法是$L$移動時利用update算式的右邊(透過指標判斷目前狀態)，查詢左邊，修改查詢都是$O(1)$，遞迴一層共$N$個，總共$logN$層，因此複雜度$O(NlogN)$。

### 5.回歸正題
這題我們排序完後把數字$N$滾動到最右邊，接著分兩種情況，$R=N$以及$R\neq N$，我們討論以下:

(1) $R\neq N$:
$1\sim N-1$這個區間是一條線的、不是環，所以可以透過問題◇以$O(NlogN)$解決。

(2) $R=N$:
還記得前面的DSU方法嗎，針對這個case可以用DSU喔!因為只需要一個$R$，為$O(N)$

結合(1)、(2)，此問題可以以時間複雜度$O(NlogN)$、空間複雜度$O(N)$解決。