[問題] ZeroJudge-c216
看板Prob_Solve (計算數學 Problem Solving)作者fatcat8127 (胖胖貓)時間5年前 (2019/04/02 17:45)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/3 (看更多)
如題，附上題目連結(https://zerojudge.tw/ShowProblem?problemid=c216)
這題是關於線段樹的操作，但是奇妙的是題目的區段更新是整體更新
(感覺有貓膩但不知道怎麼利用)，以下是兩個想法但都會出現TLE的情況。
每個節點分別紀錄區段內的長度總和和『容忍度』，容忍度的定義是更新高度時
若落在容忍度範圍內只要對這個節點的內容調整即可，子節點就透過懶惰標記延後更新。
(1)(65%) 利用懶惰標記，只有查詢區間時才 Push_down 更新的數值：
操作上的問題在於最糟的情況是每次都查詢整個區段時上面的懶惰標記就無意義
(https://www.codepile.net/pile/GoWW22oR)
(2)(72%) 根據 ZJ-c652 的啟發發現某些情況下會出現提早收斂的情況
但一樣最糟的情況還是無法改善，每次查詢都得拜訪到葉節點才會停止
(https://www.codepile.net/pile/p3bVlD3b)
不知道板上各位大大們對於這題的想法？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1554198303.A.60C.html
推
04/02 20:13,
5年前
, 1F
04/02 20:13, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
