我们将询问离线， 我们从左往右加元素， 如果当前的位置为 i ，用一棵线段树保存区间[x, i]的答案，
每次更新完， 遍历R位于 i 的询问更新答案。
我们先考虑最暴力的做法， 我们先找到位于 i 前面第一个 j， a[ j ] > a[ i ]， 那么x 属于 [ 1, j ]的答案
就会被a[ j ] - [ i ] 更新一下。 然后下一个找在 j 前面第一个 k， a[ k ] >= a[ i ] && a[ k ] < a[ j ]， 这个过程
可以用一个主席树来维护。 但是这样的做法肯定会T掉， 实际上我们多了很多没有必要的更新。
我们找 k 的时候肯定要满足这个不等式， a[ k ] - a[ i ] < a[ j ] - a[ k ] -> a[ k ] < (a[ i ] + a[ j ] ) / 2， 这样
就只要重复log(max)次就能完成。
为什么这个不等式成立呢， 因为， a[ j ] - a[ k ] 这个值在 j 加进去的时候就更新了一次，没必要找比这个值大的。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const double eps = 1e-9; const double PI = acos(-1); int n, m, a[N], ans[N * 5]; vector<PII> qus[N]; vector<int> oo; #define lson l, mid , rt << 1 #define rson mid + 1, r, rt << 1 | 1 namespace SGT1 { int a[N << 2]; void build(int l, int r, int rt) { a[rt] = inf; if(l == r) return; int mid = l + r >> 1; build(lson); build(rson); } void update(int L, int R, int val, int l, int r, int rt) { if(l >= L && r <= R) { a[rt] = min(a[rt], val); return; } int mid = l + r >> 1; if(L <= mid) update(L, R, val, lson); if(R > mid) update(L, R, val, rson); } int query(int p, int l, int r, int rt) { if(l == r) return a[rt]; int mid = l + r >> 1; if(p <= mid) return min(query(p, lson), a[rt]); else return min(query(p, rson), a[rt]); } } namespace SGT2 { int tot = 0, Rt[N]; struct Node { int mx, ls, rs; } a[N * 25]; void init() { tot = 0; } void update(int p, int val, int l, int r, int& x, int y) { x = ++tot; a[x] = a[y]; a[x].mx = max(a[x].mx, val); if(l == r) return; int mid = l + r >> 1; if(p <= oo[mid - 1]) update(p, val, l, mid, a[x].ls, a[y].ls); else update(p, val, mid + 1, r, a[x].rs, a[y].rs); } int query(int L, int R, int l, int r, int x) { if(L > oo[r - 1] || R < oo[l - 1]) return 0; if(oo[l - 1] >= L && oo[r - 1] <= R) return a[x].mx; int mid = l + r >> 1; if(R <= oo[mid - 1]) return query(L, R, l, mid, a[x].ls); else if(L > oo[mid - 1]) return query(L, R, mid + 1, r, a[x].rs); else return max(query(L, R, l, mid, a[x].ls), query(L, R, mid + 1, r, a[x].rs)); } } void solve() { oo.clear(); SGT1::build(1, n, 1); SGT2::init(); for(int i = 1; i <= n; i++) oo.push_back(a[i]); sort(oo.begin(), oo.end()); oo.erase(unique(oo.begin(), oo.end()), oo.end()); for(int i = 1; i <= n; i++) SGT2::update(a[i], i, 1, SZ(oo), SGT2::Rt[i], SGT2::Rt[i - 1]); for(int i = 2; i <= n; i++) { int cnt = 1; int now = SGT2::query(a[i], inf, 1, SZ(oo), SGT2::Rt[i - 1]); while(now) { SGT1::update(1, now, a[now] - a[i], 1, n, 1); if(a[now] == a[i]) break; int nxt = SGT2::query(a[i], a[i] + a[now] >> 1, 1, SZ(oo), SGT2::Rt[now - 1]); now = nxt; } for(auto& q : qus[i]) ans[q.se] = min(ans[q.se], SGT1::query(q.fi, 1, n, 1)); } } int main() { memset(ans, inf, sizeof(ans)); scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &m); for(int i = 1; i <= m; i++) { int L, R; scanf("%d%d", &L, &R); qus[R].push_back(mk(L, i)); } solve(); for(int i = 1; i <= n; i++) a[i] = -a[i]; solve(); for(int i = 1; i <= m; i++) printf("%d ", ans[i]); return 0; } /* */