解法一（线段树）见这里。 我们维护一棵线段树，树上每个结点用平衡树维护含有的元素，并且维护这个区间中的一个值和这个区间右边的另一个值的差的最小值。按区间的左端点从右往左扫描，每次用 ai a_i对区间 (i,n] (i,n]进行覆盖，询问的时候直接询问区间 (l,r] (l,r]最小值。 覆盖的时候一般来说需要递归到底，但是这样复杂度还不如暴力。一个重要的剪枝是维护之前已经遍历的区间的前缀最小