發表新討論
#27980: BIT可否


s0975247623@gmail.com (愛吃又愛睡的Weber)

g597. 3. 生產線 -- 2021年11月 APCS | From: [42.77.146.155] | 發表日期: 2021-11-08 09:47

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

#27981: Re:BIT可否


linlincaleb@gmail.com (臨末之頌)

g597. 3. 生產線 -- 2021年11月 APCS | From: [203.64.161.116] | 發表日期: 2021-11-08 10:21

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

沒學過BIT，但應該可以線段樹(一開始的想法)，後來才想到我有寫過b526(謝蝸牛大大放這題)

#27990: Re:BIT可否


chuan53 (eggMan)

g597. 3. 生產線 -- 2021年11月 APCS | From: [106.105.176.106] | 發表日期: 2021-11-08 12:55

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

應該可以......吧?

#27994: Re:BIT可否


rollfc (點石學園 StoneCampus)

g597. 3. 生產線 -- 2021年11月 APCS | From: [1.165.15.147] | 發表日期: 2021-11-08 17:43

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

沒學過BIT，但應該可以線段樹(一開始的想法)，後來才想到我有寫過b526(謝蝸牛大大放這題)


同樣是差分的練習還有：

e841: P8. 幽靈寶藏(Treasure) 和 Atcoder - 221D - Online games

另外 a014: 夾娃娃(由 morris1028 (碼畜) 上傳的經典題)

APCS 的 P3/ P4 會有一題可以硬砸 BIT/ SegmentTree 的題目但多半時候可以透過 D&C 或是 STL 繞開這個技巧

有時候只要找極值問題就不大但是如果是這次會牽涉到區間更新這類，透過線段樹的延遲標記 或是 BIT 轉差分時就變得格外不友善

#27998: Re:BIT可否


s0975247623@gmail.com (愛吃又愛睡的Weber)

g597. 3. 生產線 -- 2021年11月 APCS | From: [42.77.146.155] | 發表日期: 2021-11-08 21:15

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

沒學過BIT，但應該可以線段樹(一開始的想法)，後來才想到我有寫過b526(謝蝸牛大大放這題)


同樣是差分的練習還有：

e841: P8. 幽靈寶藏(Treasure) 和 Atcoder - 221D - Online games

另外 a014: 夾娃娃(由 morris1028 (碼畜) 上傳的經典題)

APCS 的 P3/ P4 會有一題可以硬砸 BIT/ SegmentTree 的題目但多半時候可以透過 D&C 或是 STL 繞開這個技巧

有時候只要找極值問題就不大但是如果是這次會牽涉到區間更新這類，透過線段樹的延遲標記 或是 BIT 轉差分時就變得格外不友善


大感謝 真不曉得當初為什麼沒有回想起區間修改的問題XD

#28016: Re:BIT可否


r1cky (hehe)

g597. 3. 生產線 -- 2021年11月 APCS | From: [114.32.128.128] | 發表日期: 2021-11-10 06:31

在考APCS的時候有想到Greedy

但唯一想到不會TLE的資結是BIT (目前看到的詳解都是差分，沒學到

想請問是我自己BIT刻爛了還是真的沒法用

不用BIT啦

假設我們最後加起來每台機器的結果是a1 a2 a3 a4 a5 a6 a7 a8…

我們令di = ai-a(i-1) 就是d的第i項等於a第i項減去a的再前一項（純差分）

然後我們令a0=0（前面再塞一項）

這樣我們修改時只要改兩個d（修改範圍前後那兩個）

而所求a就是：

a1=d1 

a2=d1+d2（會消掉）

a3=d1+d2+d3

……

ZeroJudge Forum