《穿越火线》是一款第一人称射擊游戏的网络游戏玩家扮演控制一名持枪战斗人员,与其他玩家进行械斗
给定一个长度为 n n n的序列 a a a问每个長度为 K K K的连续区间的最长贪心上升子序列有多长。
开始看错题叻,以为就是区间最长上升子序列然而正确的题目似乎性质更显然了。
我们按题意进行连边会形成一个森林再新建一个节点作为超级根。
那么实际上对于每个询问的区间来说对应了树上的一些节点,我们就是要求树在只看这些节点时节点最大深度(两关键点间的路径看作权 1 1 1)
这个问题可以这样做:首先求出树的 DFS \text{DFS} DFS序,那么若一个节点有贡献对应的就是子树 + 1 +1 +1询问就是全局的 max