發表新討論
#24475: 線段樹


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
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.217.8]
最後登入時間 ：
2024-04-13 22:06:23
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.136.219]
最後登入時間 ：
2023-09-13 16:25:16
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