#26915: 線段樹有可能過嗎?


andrew99154 (YuCheng)

School : 均一國際教育實驗高級中學
ID : 145338
IP address : [111.242.180.203]
Last Login :
2022-03-14 08:51:52
f855. 線段覆蓋長度 加強版 -- APCS | From: [111.241.39.83] | Post Date : 2021-09-01 18:07

原本在b966硬輾過,想說來挑戰看看這題。

區間修改值,想到的做法是線段樹,

但依照題目,10^7的陣列要開四倍大小的線段樹才會過,也就是至少要開4*(10^7)的陣列大小。

可是我一直踩到segmentation fault。

看到版主有在b966說線段樹是標準解,想請問是怎麼過的呢?

 
#26916: Re:線段樹有可能過嗎?


rollfc (胖胖貓)

School : 國立交通大學
ID : 81012
IP address : [1.170.230.228]
Last Login :
2022-05-17 21:28:18
f855. 線段覆蓋長度 加強版 -- APCS | From: [114.34.200.113] | Post Date : 2021-09-01 18:12

原本在b966硬輾過,想說來挑戰看看這題。

區間修改值,想到的做法是線段樹,

但依照題目,10^7的陣列要開四倍大小的線段樹才會過,也就是至少要開4*(10^7)的陣列大小。

可是我一直踩到segmentation fault。

看到版主有在b966說線段樹是標準解,想請問是怎麼過的呢?


他提到的線段樹應該是有預先做了 離散化,點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )

如果不理解什麼是離散化,你可以查一下吳邦一教授編寫的 AP325

 
#26917: Re:線段樹有可能過嗎?


andrew99154 (YuCheng)

School : 均一國際教育實驗高級中學
ID : 145338
IP address : [111.242.180.203]
Last Login :
2022-03-14 08:51:52
f855. 線段覆蓋長度 加強版 -- APCS | From: [111.241.39.83] | Post Date : 2021-09-01 18:28

原本在b966硬輾過,想說來挑戰看看這題。

區間修改值,想到的做法是線段樹,

但依照題目,10^7的陣列要開四倍大小的線段樹才會過,也就是至少要開4*(10^7)的陣列大小。

可是我一直踩到segmentation fault。

看到版主有在b966說線段樹是標準解,想請問是怎麼過的呢?


他提到的線段樹應該是有預先做了 離散化,點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )

如果不理解什麼是離散化,你可以查一下吳邦一教授編寫的 AP325

了解,我再參考一下相關資料,謝謝解惑!

 
#26927: Re:線段樹有可能過嗎?


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [114.25.67.14]
Last Login :
2022-05-17 19:45:08
f855. 線段覆蓋長度 加強版 -- APCS | From: [111.243.18.144] | Post Date : 2021-09-02 17:37

本題不需要用到線段樹喔! 我寫那篇當下沒有想到更簡單的方法,所以誤導您了抱歉

這題只需要用到排序 不過用線段樹+離散化也是可以啦

 
ZeroJudge Forum