题目描述

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$,每次询问一个区间 $[l,r]$ 内差值最小的两个数的差值。

思路

考虑离线询问,将询问按照右端点排序,然后维护左端点的答案。我们先只统计对于 $j < i, a_j > a_i$ 的贡献,对于 $a_j < a_i$ 的贡献,我们把权值全部取反再做一次就行了。

设当前的右端点位于 $i$,我们就需要找对于满足 $a_j > a_i, j < i$ 的最大的 $j$,更新左端点区间 $[1,j]$ 的答案,然后找一个 $a_i < a_{j’} < a_j,j'<j$ 的点,一直这么做下去。

注意找直接这样更新复杂度是不正确的,我们需要减少向左查询的次数。发现下一次寻找的 $j’$ 除了满足以上所说的条件之外,还需要满足 $a_j − a_{j’} > a_{j’} − a_i$,否则这次更新是没有意义的。这个判断保证每次查询都使得 $a_{j’}-a_{i}$ 减半,复杂度降至 $\Theta(n\log n\log 10^9)$。

代码