---
# System prepended metadata

title: '【題解APCS】d101: Q-7-11. 紅白彩帶 (APCS201902)'

---

#### 題目：https://judge.tcirc.tw/ShowProblem?problemid=d101
這題n跟k都可以到很大，暴力解容易TLE
```C++=
#include <iostream>
#include <set>
using namespace std;
 
const int maxn = 100005;
int n, k, c[maxn], length[maxn], mx, mn;
multiset <int> st;
 
void change(int x){
    length[x] = length[x-1] + length[x+1] + 1;
    st.insert(length[x]);

    if(length[x+1] != 0)
        st.erase(st.find(length[x+1]));     // 移除這段長度
        length[x+length[x+1]] = length[x];  // 把頭尾改成長度
    if(length[x-1] != 0)
        st.erase(st.find(length[x-1]));
        length[x-length[x-1]] = length[x];
}
 
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> c[i];
        if (c[i] == 1){
            change(i);
        }
    }
    if(!st.empty()){
        mx += *st.rbegin();
        mn += *st.begin();
    }
    for (int i = 1; i <= k; i++){
        int q;
        c[q] = 1;
        cin >> q;
        change(q);
        mx += *st.rbegin();
        mn += *st.begin();
    }
    cout << mx << endl << mn;
}
```
### 逐步看length陣列發生什麼事情
這份程式的邏輯是
每填一個顏色就check前後，如果length不等於0就代表要連接，並從multiset中erase掉那一段長度

從範例輸入來看各陣列和集合的變化可能會比較好理解
```
9 3
0 1 1 0 0 1 0 1 0
5 1 7
```
c 陣列負責儲存彩帶顏色資料
length 陣列儲存他們的長度訊息
st 儲存彩帶的長度
(下面length用l表示)

- ### 一開始全都是白色
    ```
    c : 0 0 0 0 0 0 0 0 0
    l : 0 0 0 0 0 0 0 0 0
    st = {}
    ```

- ### cin 第一個 1
    ```
    c : 0 1 0 0 0 0 0 0 0
    l : 0 1 0 0 0 0 0 0 0
    st = {1}
    ```

- ### cin 第二個 1
    cin後進入change函式，發現前一個的length是1，所以自己的length變成1+1=2
    ```
    c : 0 1 1 0 0 0 0 0 0
    l : 0 2 2 0 0 0 0 0 0
    st = {2}
    ```
- ### cin 第三個 1
    ```
    c : 0 1 1 0 0 1 0 0 0
    l : 0 2 2 0 0 1 0 0 0
    st = {1, 2}
    ```

- ### cin 第三個 1
    ```
    c : 0 1 1 0 0 1 0 1 0
    l : 0 2 2 0 0 1 0 1 0
    st = {1, 1, 2}
    ```
    
- ### 第一個填色(5)
    ```
    c : 0 1 1 0 1 1 0 1 0
    l : 0 2 2 0 2 2 0 1 0
    st = {1, 2, 2}
    ```
    
- ### 第二個填色(1)
    ```
    c : 1 1 1 0 1 1 0 1 0
    l : 3 2 3 0 2 2 0 1 0
    st = {1, 2, 3}
    ```
- ### 第三個填色(7)
    ```
    c : 1 1 1 0 1 1 1 1 0
    l : 3 2 3 0 4 2 4 4 0
    st = {3, 4}
    ```
每段彩帶的頭尾都會變成那段彩帶的長度
