s0975247623@gmail.com
(愛吃又愛睡的Weber)
學校
:
高雄市立高雄高級中學
編號 : 136210
來源 : [42.77.23.117]
最後登入時間 ：
2023-01-17 20:53:17
linlincaleb@gmail.com
(臨末之頌)
學校
:
新北市立板橋高級中學
編號 : 132772
來源 : [203.64.161.123]
最後登入時間 ：
2024-07-29 10:02:49
在考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 轉差分時就變得格外不友善
s0975247623@gmail.com
(愛吃又愛睡的Weber)
學校
:
高雄市立高雄高級中學
編號 : 136210
來源 : [42.77.23.117]
最後登入時間 ：
2023-01-17 20:53:17
在考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
在考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
……