發表新討論
#24475: 線段樹


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.89.50]
最後登入時間 ：
2025-09-24 12:11:30
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)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.89.50]
最後登入時間 ：
2025-09-24 12:11:30
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 (游翔宇)

學校 : 國立宜蘭高級中學
編號 : 98903
來源 : [140.113.121.154]
最後登入時間 ：
2024-09-03 19:11:45
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