此題為這題的困難版,差別在於有修改操作且可能會詢問多次不同的區間。
$\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]$ 的馬桶,最多可以有幾個人同時使用。
對於每筆 $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\%:無特別限制$
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|