问题

给出一个长度为\(n\)的序列\(a[i]\)，有\(m\)次询问，
每次给你一个\(k\)，让你求一个最长子串\([l,r]\)，使得\(max_l^r\{a_i\}-min_l^r\{a_i\}\leq k\)

思路一

我们显然可以看出这个长度是具有单调性的，于是我们二分答案
\(check\)的方式有以下几种

RMQ

需要\(nlogn\)的时间预处理，空间也要\(nlogn\)
预处理好最大和最小的\(st\)表，\(O(n)\)扫一遍即可

单调队列

时间空间都只需要\(O(n)\)
维护一个单调增的和一个单调减的队列，保持长度即可

不管采用哪种\(check\)，思路一的做法都是\(O(nmlogn)\)的

思路二

想一下如果是朴素的暴力，
我们枚举一个必选的右端点\(i\)，一定有一个最远的左端点
但是，这个左端点下标是单调不减的！
所以直接单调队列即可。。

证明

很简单，如果右端点是\(i\)的情况下最远的左端点是\(j\)
那么对于右端点\(i',i'>i\)，假设左端点\(j'<j\)
因为\(max_j^i\{a_i\}-min_j^i\{a_i\}\leq k\)，而\(j\)是最左端点
所以一定有\(max_{j'}^i\{a_i\}-min_{j'}^i\{a_i\}> k\)
根据放缩法，\(max_{j'}^{i'}\{a_i\}-min_{j'}^{i'}\{a_i\}> k\)
O了

巴特西

关于求最长子串，使得最大减最小小于k的问题-以POJ4003为例

问题

思路一

RMQ

单调队列

思路二

证明

最新文章

热门文章