發表新討論
#24475: 線段樹


fire5386 (becaidorz)

b966. 3. 線段覆蓋長度 -- 2016年3月 apcs | From: [61.230.46.160] | 發表日期: 2021-02-23 20:31

本題的標準解答為線段樹

建議加上測資n=9999且每個l, r都是l=0, r=9999999

這樣暴力解絕對會超時O(n*mxn) 其中mxn為總線段最長的長度(9999999)

#24741: Re:線段樹


fire5386 (becaidorz)

b966. 3. 線段覆蓋長度 -- 2016年3月 apcs | From: [61.230.17.252] | 發表日期: 2021-03-19 20:20

本題的標準解答為線段樹

建議加上測資n=9999且每個l, r都是l=0, r=9999999

這樣暴力解絕對會超時O(n*mxn) 其中mxn為總線段最長的長度(9999999)


其實也不用線段樹。基本的排序就可以了

#27559: Re:線段樹


bryan931218@gmail.com (游翔宇)

b966. 3. 線段覆蓋長度 -- 2016年3月 apcs | From: [118.169.132.55] | 發表日期: 2021-10-13 19:30

本題的標準解答為線段樹

建議加上測資n=9999且每個l, r都是l=0, r=9999999

這樣暴力解絕對會超時O(n*mxn) 其中mxn為總線段最長的長度(9999999)

把每個線段起點的大小排序就行了

ZeroJudge Forum