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

內容

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

$\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]$ 的馬桶最多同時可以有幾個人使用。

範例輸入 #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) ]

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