#26915: 線段樹有可能過嗎？
andrew99154
(YuCheng)
學校
:
均一國際教育實驗高級中學
編號 : 145338
來源 : [111.254.45.176]
最後登入時間 ：
2024-01-03 20:33:30
f855. 第 3 題 線段覆蓋長度 測資加強版
--
APCS大學程式設計先修檢測(2016/03/05)
| From: [111.241.39.83] |
發表日期
:
2021-09-01 18:07
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
#26916: Re:線段樹有可能過嗎？
f855. 第 3 題 線段覆蓋長度 測資加強版
--
APCS大學程式設計先修檢測(2016/03/05)
| From: [114.34.200.113] |
發表日期
:
2021-09-01 18:12
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
他提到的線段樹應該是有預先做了 離散化，點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )
如果不理解什麼是離散化，你可以查一下吳邦一教授編寫的 AP325
#26917: Re:線段樹有可能過嗎？
andrew99154
(YuCheng)
學校
:
均一國際教育實驗高級中學
編號 : 145338
來源 : [111.254.45.176]
最後登入時間 ：
2024-01-03 20:33:30
f855. 第 3 題 線段覆蓋長度 測資加強版
--
APCS大學程式設計先修檢測(2016/03/05)
| From: [111.241.39.83] |
發表日期
:
2021-09-01 18:28
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
他提到的線段樹應該是有預先做了 離散化，點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )如果不理解什麼是離散化，你可以查一下吳邦一教授編寫的 AP325
了解，我再參考一下相關資料，謝謝解惑！
#26927: Re:線段樹有可能過嗎？
f855. 第 3 題 線段覆蓋長度 測資加強版
--
APCS大學程式設計先修檢測(2016/03/05)
| From: [111.243.18.144] |
發表日期
:
2021-09-02 17:37
本題不需要用到線段樹喔！ 我寫那篇當下沒有想到更簡單的方法，所以誤導您了抱歉
這題只需要用到排序 不過用線段樹+離散化也是可以啦
ZeroJudge Forum