题意

每次询问一个区间中,所有长度为 \(w\) 的连续子数列中最小值的最大值。

分析

最小值的最大值,很容易想到二分。

于是考虑对于每一个询问二分答案。于是考虑如何验证答案。

验证答案需要知道,当前区间中高度 \(\ge mid\) 的连续长度是否 \(\ge w\) 。

一个比较常规的套路,就是区间中 \(\ge mid\) 的设为 \(1\) ,其余为 \(0\) ,维护连续 \(1\) 的长度。

考虑用线段树维护,只需要记录每一个区间中最长的长度、左端点开始连续的长度、右端点开始连续的长度(合并的时候需要)即可。

而需要针对每一个 \(mid\) 建立线段树显然是不可能的,考虑到每次询问的都是 \(\ge mid\) 的情况,于是可以按照每一块的高度从大到小插入,用主席树维护。于是就变成了一个前缀版本的查询。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注