h990: Waimai 超人與 Hehe 遊俠 (Hard Version)
Tags : BIT 數學 線段樹
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-19 19:04

Content

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

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

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

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

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

Input

第一行有兩個正整數 $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$
Output

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

Sample Input #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
Sample Output #1
1
3
0
4
2
2
3
2
1
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
Hint :

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

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

Tags:
BIT 數學 線段樹
出處:
第六屆簡單的小競賽 [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」