e084. Q-5-8. 完美彩帶(同 Q-3-12，分治版)(APCS201906)

Content

有一條細長的彩帶，總共有 m 種不同的顏色，彩帶區分成 n 格，每一格的長度都是 1，每一格都有一個顏色，相鄰可能同色。長度為 m 的連續區段且各種顏色都各出現一次，則稱為「完美彩帶」。請找出總共有多少段可能的完美彩帶。請注意，兩段完美彩帶之間可能重疊。

Time limit: 1 秒

Input

第一行為整數 m 和 n，滿足 2 <= m <= n <= 2 <= 105；第二行有 n 個以空白間隔的數字，依序代表彩帶從左到右每一格的顏色編號，顏色編號是不超過 10e9 的非負整數，每一筆測試資料的顏色數量必定恰好為 m。

Output

有多少段完美彩帶。

Sample Input

4 10
1 4 1 7 6 4 4 6 1 7

Sample Output

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <10M
公開測資點#1 (20%): 1.0s , <10M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

說明：區間[2, 5]是一段完美彩帶，因為顏色 4、1、7、6 剛好各出現一次，此外，區間[3, 6]與[7, 10]也都是完美彩帶，所以總共有三段可能的完美彩帶。

Tags:

分治

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」