d036: 習題 Q-3-12. 完美彩帶 (同 Q-5-8 ,分治版) (APCS201906)
Tags : sweep line
Accepted rate : 169人/180人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-13 10:08

Content

有一條細長的彩帶,總共有 $m$ 種不同的顏色,彩帶區分成 $n$ 格,每一格的長度都是 1,每一格都有一個顏色,相鄰可能同色。

長度為 $m$ 的連續區段且各種顏色都各出現一次,則稱為「完美彩帶」。

請找出總共有多少段可能的完美彩帶。請注意,兩段完美彩帶之間可能重疊。

Input

第一行為整數 $m$ 和 $n$,滿足 $2 \leq m \leq n \leq 2*10^5$;

第二行有 $n$ 個以空白間隔的數字,依序代表彩帶從左到右每一格的顏色編號,

顏色編號是不超過 $10^9$ 的非負整數,每一筆測試資料的顏色數量必定恰好為 $m$。

Output

有多少段完美彩帶。

Sample Input #1
4 10
1 4 1 7 6 4 4 6 1 7
Sample Output #1
3
測資資訊:
記憶體限制: 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 :
Tags:
sweep line
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
145
spng (david)
d036
python 解題影片
73 2023-02-24 20:09