[问题] 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