0 Judge
Code: 0
資工の詹皇最近遇到了一個麻煩:他的私人花園裡跑進了一些蘿莉。根據貓科動物學家GYLin,蘿莉 ( Felis lolitus ) 是一種適應力極強的貓科動物,在世界各地都有族群擴大的跡象。而詹皇花園中種的花剛好都是他們最喜歡吃的品種。這些蘿莉破壞力高又善於躲藏,把詹皇的花園搞得一蹋糊塗,氣憤又無奈的他前來尋求各位的幫助。
首先,介紹一下詹皇的花園:花園裡有 $N$ 朵花,而且他喜歡將花種成整齊的一排;因此花園中的花可以用一個序列表示:$A_1, A_2 … A_N$,其中 $A_i$ 代表從左到右第 $i$ 朵花的品種。
好消息是,這些蘿莉雖然善於躲藏,但他們有一個怪異的習性:他們只會躲在漂亮位置上。一個漂亮位置是一個漂亮區間上的任何位置:如果花園中的一個區間 $[ i, i+1, … , j ]$ 其中的每朵花的品種都只在該區間出現一次,且區間的長度至少有 $K$ ,則區間 $[i, j]$ 就是一個漂亮區間。
你的任務是幫詹皇找出所有漂亮位置,好讓他能抓到所有的蘿莉。
每筆測資只會有兩行。其中第一行包含三個整數 $N$ $M$ $K$ ,分別代表:
$N$ :詹皇花園中花的總數
$M$ :花園中總共有幾種花
$K$ :一個漂亮區間的最短長度
接著第二行會有 $N$ 個整數 $A_1 … A_N$ ,其中 $A_i$ 代表從左開始第 $i$ 朵花的品種。
$1 \leq N,M,K \leq 10^6$
$1 \leq A_i \leq M$ 對任意 $i$
$1 \leq K \leq \min(N,M)$
首先輸出一個整數 $C$ ,代表花園中漂亮位置的總數。
如果 $C > 0$ ,在第二行從小到大輸出這些漂亮位置。
(注意請不要在最後的數字輸出多餘空格,但如大部分其他題目,最後請換行)
6 3 2
1 1 2 2 3 3
4
2 3 4 5
9 3 3
1 1 1 2 2 2 3 3 3
0
13 8 3
1 8 7 1 1 1 8 7 7 7 8 7 1
10
1 2 3 4 6 7 8 11 12 13
在第一筆測資,花園中只有兩個漂亮區間:
1 [1 2] 2 3 3
1 1 2 [2 3] 3
而至少被一個漂亮區間包含的位置為: 2, 3, 4, 5 ,換言之,這些就是所有的漂亮位置。
在第二筆測資中,顯然由於 $K$ 的限制,花園中不存在任何漂亮區間 -- 沒有任何長度 $\geq 3$ 的區間,其中每一朵花的品種都只在該區間出現一次。
在第三筆測資中,花園裡總共有四個漂亮區間:
[1 8 7] 1 1 1 8 7 7 7 8 7 1
1 [8 7 1] 1 1 8 7 7 7 8 7 1
1 8 7 1 1 [1 8 7] 7 7 8 7 1
1 8 7 1 1 1 8 7 7 7 [8 7 1]
test case #1~4: $N,M,K<=1000$ (score: 20)
test case #5~10: $N,M,K<=10^6$ (score: 80)