在NFLS模拟赛上遇到的，赛后订正过的。隔了蛮长时间的，总结一下。首先转化为笛卡尔树上后缀前缀的问题。然后考虑如何转移，发现转移形如\(f(x)=\min\{f(x)+C,kx+b\}\)的形式。可以直接线段树维护每个点的最优直线，在update的时候：如果\(f(x)+C\lekx+b\)恒成立（左右

思路线段树。题意可以转化成每次判定有多少个前缀满足所有结点构成矩形。首先排除确定矩阵坐标再数答案的做法，因为太难。所以考虑如何对前缀进行判定。一个简单的想法是维护前\(i\)个点中\(x,y\)坐标的最值，但这样只能暴力看矩阵中的所有元素，跑得很慢。不妨思考一下合法

题目分析这个题本身很简单，可能就是因为是IOI题所以看上去就难了些吧。其实题目就是让我们先走一段全部大于等于\(l\)的点然后再走一段全部小于等于\(r\)的点，那么能

43AT_mujin_pc_2017_dOrientedTree头痛，想不了题。。。大概就是在直径重点断开，然后每棵子树都dp一下。先放一边吧。44P4899[IOI2018]werewolf狼人一个想法是