[問題] ZeroJudge-c216(已解決)

作者: fatcat8127 (胖胖貓)   2019-04-02 17:44:59
如題,附上題目連結(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)
不知道板上各位大大們對於這題的想法?
作者: GYLin (Lynx)   2019-04-02 20:13:00
剛剛用個很醜的預處理AC了XD 等等回文

Links booklink

Contact Us: admin [ a t ] ucptt.com