题意

给定一个长度为n的数列,有m次询问,询问形如l r k

要你在区间[l,r]内选一个长度为k的区间,求区间最小数的最大值


首先考虑 二分这个答案mid

问题转换为判断答案是否成立

然后可以按照套路把比mid大的设成1,

比mid小的设成0 对于每一个mid创建一个线段树

线段树维护最长连续的1就行了

线段树结点num表示区间最长的连续1,

lnum表示从左边开始连续的1,rnum表示从右边开始的连续的1,然后合并的时候大力讨论就行了

但是对于多组询问就有点问题了

考虑整体二分,不过对于每个mid值建线段树不符合整体二分的基本法…

可以重复利用建好的线段树!

先处理比mid大的,然后处理比mid小的

 


说点什么

avatar
  Subscribe  
提醒