APCS201902第2題紅白彩帶

一條彩帶被分成 n 個相同大小的格子，有的格子是紅色，有些則是白色。

小軒拿到彩帶後開始塗顏色，每次會將一個白色格子塗滿紅色，然後小軒會算一算目前最長與最短紅色區域的長度佔了幾格，相鄰的紅色格子就屬於同一個紅色區域。小軒一共塗了 k 次，

請你計算出每一次紅色區域的最大與最小長度，並輸出個別的總和。

彩帶可以看成一維陣列，以 0 表示白色，而 1 表示紅色。彩帶的格子從 1 開始由左而右依序編號，小軒每次將某個格子塗上紅色。

以下是一個例子。

格子編號 1 2 3 4 5 6 7 8 9

剛開始的彩帶 0 1 1 0 0 1 0 1 0

一開始紅色區域最大的長度是 2，最小的長度是 1。

第1次塗在第5格後 0 1 1 0 1 1 0 1 0

第1次塗完後最長的紅色區域有 2 塊，長度都是 2，最小的長度是 1。

第2次塗在第1格後 1 1 1 0 1 1 0 1 0

第2次塗完後紅色區域的最大長度是3，最小長度是1。

第3次塗在第7格後 1 1 1 0 1 1 1 1 0

第3次塗完後紅色區域的最大長度是4，最小長度是3。

以這個例子而言，每一次(包含剛開始) 紅色區域的最大長度總和是 2+2+3+4=11；

而紅色區域的最小長度總和是 1+1+1+3=6。

輸入說明

輸入有三行，第一行是兩個整數，依序是 n 與 k ，代表彩帶長度以及小軒塗色的次數，n≤1e5 、 k≤2e4 。

第二行有 n 個 0 或 1 的數字，依序代表彩帶第 1 格至第 n 格的顏色， 0 代表白色， 1 代表紅色。

第三行有 k 個數字，依序代表每一次塗紅色的格子編號，若 k=0 ，則第三行為空行。同一行數字之間都是以空白間隔。小軒每次一定都塗在白色格子上，而且最大的紅色區域長度不會超過 1e4 。

輸出說明

輸出兩行，

第一行是每次紅色區域最大長度的總和，

第二行是每次紅色區域最小長度的總和。

輸入範例1

5 1

1 0 1 0 1

輸出範例1

輸入範例2

9 3

0 1 1 0 0 1 0 1 0

5 1 7

輸出範例2

解題策略

使用map，map的key表示紅色範圍的開始，map的value表示紅色範圍的結束，合併相鄰紅色區塊，產生更大區塊。使用multiset紀錄每個區段的長度，最後找出最大與最小長度。