#26915: 線段樹有可能過嗎？
andrew99154
(YuCheng)
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
#26916: Re:線段樹有可能過嗎？
rollfc
(點石學園 StoneCampus)
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
他提到的線段樹應該是有預先做了 離散化，點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )
如果不理解什麼是離散化，你可以查一下吳邦一教授編寫的 AP325
#26917: Re:線段樹有可能過嗎？
andrew99154
(YuCheng)
原本在b966硬輾過，想說來挑戰看看這題。
區間修改值，想到的做法是線段樹，
但依照題目，10^7的陣列要開四倍大小的線段樹才會過，也就是至少要開4*(10^7)的陣列大小。
可是我一直踩到segmentation fault。
看到版主有在b966說線段樹是標準解，想請問是怎麼過的呢？
他提到的線段樹應該是有預先做了 離散化，點的位置雖然介於( 0, 1e7 ) 但點的數量不超過 1e4 * 2( 起點+終點 )如果不理解什麼是離散化，你可以查一下吳邦一教授編寫的 AP325
了解，我再參考一下相關資料，謝謝解惑！
#26927: Re:線段樹有可能過嗎？
fire5386
(becaidorz)
本題不需要用到線段樹喔！ 我寫那篇當下沒有想到更簡單的方法，所以誤導您了抱歉
這題只需要用到排序 不過用線段樹+離散化也是可以啦