h990. Waimai 超人與 Hehe 遊俠 (Hard Version)

內容

此題為這題的困難版，差別在於有修改操作且可能會詢問多次不同的區間。

$Waimai$ 超人與 $Hehe$ 遊俠組成的英雄團體「 $Waimaihehe$ 」常常打擊罪犯，再壞的壞人，聽到「 $Waimaihehe$ 」這個詞後都會嚇得聞風喪膽。

只是打擊罪犯雖然能獲得民眾的愛戴，但是卻不能賺錢，所以 $Waimai$ 超人與 $Hehe$ 遊俠必須要去打工。

今天他們的工作是當清潔工，他們的要做的就是刷馬桶，一共有 $n$ 個馬桶，有些馬桶是正在被刷的馬桶，其他人無法使用，而沒有被刷的馬桶就可以使用。 $Waimai$ 超人與 $Hehe$ 遊俠觀察到一個有趣的現象，如果某個馬桶正在被刷，或是它相鄰的馬桶有人正在使用，那其他人就不會使用這個馬桶。

馬桶可能會被刷，就不能使用了，或是刷好了，可以來使用。 $Waimai$ 超人與 $Hehe$ 遊俠想要問你：若今天開放使用的馬桶區間是 $[l, r]$ ，那最多有幾個馬桶可以同時被使用呢？

輸入說明

第一行有兩個正整數 $n, q$ ，代表有幾個馬桶和操作的次數。

第二行有 $n$ 個數字，代表由左到右第 $1 \sim n$ 個馬桶的狀態，若狀態 $= 1$ ，代表此馬桶沒有被刷，可以使用，若狀態 $= 0$ ，代表此馬桶正在被刷，不能使用。

接下來 $q$ 行，每行第一個數字為 $t y$ 。若 $t y = 1$ ，會接著輸入一個整數 $p$ ，代表由左到右位置 $p$ 的馬桶狀態改變了，也就是沒被刷的變成被刷的，被刷的變成沒被刷的；若 $t y = 2$ ，會接著輸入兩個整數 $l, r$ ，代表想要問你若今天開放了區間 $[l, r]$ 的馬桶，最多可以有幾個人同時使用。

$1 \leq n, q \leq 10^{5}$
$1 \leq t y \leq 2$
$1 \leq p \leq n$
$1 \leq l \leq r \leq n$

輸出說明

對於每筆 $t y = 2$ 的操作，輸出一個整數，代表區間 $[l, r]$ 的馬桶最多同時可以有幾個人使用。

範例輸入 #1

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

測資資訊：

記憶體限制： 80 MB
公開測資點#0 (20%): 2.0s , <10M
公開測資點#1 (20%): 2.0s , <10M
公開測資點#2 (20%): 2.0s , <10M
公開測資點#3 (20%): 2.0s , <10M
公開測資點#4 (20%): 2.0s , <10M

提示：

在範例中，每筆詢問時的馬桶狀態如下：

$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 % ：無特別限制$

標籤:

BIT 數學線段樹

出處:

第六屆簡單的小競賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」