此題為這題的困難版，差別在於有修改操作且可能會詢問多次不同的區間。
$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠組成的英雄團體「$\text{Waimaihehe}$」常常打擊罪犯，再壞的壞人，聽到「$\text{Waimaihehe}$」這個詞後都會嚇得聞風喪膽。
只是打擊罪犯雖然能獲得民眾的愛戴，但是卻不能賺錢，所以 $\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠必須要去打工。
今天他們的工作是當清潔工，他們的要做的就是刷馬桶，一共有 $n$ 個馬桶，有些馬桶是正在被刷的馬桶，其他人無法使用，而沒有被刷的馬桶就可以使用。$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠觀察到一個有趣的現象，如果某個馬桶正在被刷，或是它相鄰的馬桶有人正在使用，那其他人就不會使用這個馬桶。
馬桶可能會被刷，就不能使用了，或是刷好了，可以來使用。$\text{Waimai}$ 超人與 $\text{Hehe}$ 遊俠想要問你：若今天開放使用的馬桶區間是 $[l, r]$，那最多有幾個馬桶可以同時被使用呢？
第一行有兩個正整數 $n, q$，代表有幾個馬桶和操作的次數。
第二行有 $n$ 個數字，代表由左到右第 $1\sim n$ 個馬桶的狀態，若狀態 $= 1$，代表此馬桶沒有被刷，可以使用，若狀態 $= 0$，代表此馬桶正在被刷，不能使用。
接下來 $q$ 行，每行第一個數字為 $ty$。若 $ty = 1$，會接著輸入一個整數 $p$，代表由左到右位置 $p$ 的馬桶狀態改變了，也就是沒被刷的變成被刷的，被刷的變成沒被刷的；若 $ty = 2$，會接著輸入兩個整數 $l, r$，代表想要問你若今天開放了區間 $[l, r]$ 的馬桶，最多可以有幾個人同時使用。
- $1 \leq n, q \leq 10^5$
- $1 \leq ty \leq 2$
- $1 \leq p \leq n$
- $1 \leq l \leq r \leq n$
對於每筆 $ty = 2$ 的操作，輸出一個整數，代表區間 $[l, r]$ 的馬桶最多同時可以有幾個人使用。
10 15 0 0 0 1 1 0 1 0 1 1 1 2 1 1 2 3 5 2 4 10 2 3 3 1 9 2 1 10 2 4 7 1 4 2 3 9 2 2 7 2 4 7 2 3 6 1 3 2 6 9
1 3 0 4 2 2 3 2 1 1
在範例中，每筆詢問時的馬桶狀態如下：
$ 1 : \{0, 1, 0, 1, 1, 0, 1, 0, 1, 1\}$
$ 2 : \{1, 1, 0, 1, 1, 0, 1, 0, 1, 1\}$
$ 3 : \{1, 1, 0, 1, 1, 0, 1, 0, 1, 1\}$
$ 4 : \{1, 1, 0, 1, 1, 0, 1, 0, 1, 1\}$
$ 5 : \{1, 1, 0, 1, 1, 0, 1, 0, 1, 1\}$
$ 6 : \{1, 1, 0, 1, 1, 0, 1, 0, 0, 1\}$
$ 7 : \{1, 1, 0, 1, 1, 0, 1, 0, 0, 1\}$
$ 8 : \{1, 1, 0, 1, 1, 0, 1, 0, 0, 1\}$
$ 9 : \{1, 1, 0, 0, 1, 0, 1, 0, 0, 1\}$
$ 10 : \{1, 1, 0, 0, 1, 0, 1, 0, 0, 1\}$
$ 11 : \{1, 1, 0, 0, 1, 0, 1, 0, 0, 1\}$
$ 12 : \{1, 1, 0, 0, 1, 0, 1, 0, 0, 1\}$
$ 13 : \{1, 1, 0, 0, 1, 0, 1, 0, 0, 1\}$
$ 14 : \{1, 1, 1, 0, 1, 0, 1, 0, 0, 1\}$
$ 15 : \{1, 1, 1, 0, 1, 0, 1, 0, 0, 1\}$
在詢問 $3$ 問了區間 $[3, 5]$ 可使用的馬桶數，可使用第 $4$ 個馬桶；在詢問 $4$ 問了區間 $[4, 10]$ 可使用的馬桶數，可使用第 $4, 7, 9$ 個馬桶；在詢問 $5$ 問了區間 $[3, 3]$ 可使用的馬桶數，沒有馬桶可使用。
---------------------------------------------------------------------
$100\%：無特別限制$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||