ANS明显是有二分性的
二分答案,设二分值为b
M(i,j)−m(i,j)j−i+k>b
显然当l<长度<r时，一端是最小值，一端是最大值。
等于l或r的时候因为可能不满足以上性质，所以RMQ暴力O(nlogn)做。
a[i]−a[j]>b∗j−b∗i+b∗k 或 a[j]−a[i]>b∗j−b∗i+b∗k
那么
(a[i]+b∗i)−(a[j]+b∗j)>b∗k 或 (−a[i]+b∗i)−(−a[j]+b∗j)>b∗k
是一个单调队列的样子
原文：http://www.cnblogs.com/myx12345/p/5017606.html