Solution 1 Mo's Algorithm & Linked List
不会。。果断莫队
当插入一个数的时候，如果用set维护前驱后继，然后结果是：$O((n + m)\sqrt{n}\log n)$，没救的，卡不过去。
但是感觉原序列不会改变，使用set维护很浪费。
考虑链表，链表上的每个数的后继是这个数的后继。
考虑可以通过排序提前得到大小关系，不断从链表中删数就能得到它在剩下的区间内的前后继。如果询问在同一个块内直接暴力。否则把答案分成三部分。
- 两个数都在当前块外，先从小到大加入剩下的所有数，从右到左删掉它们，再从左到右不断加入它们，然后就能得到所有前缀的答案。
- 两个数都在当前块内，处理出所有后缀的答案，做法类似。
- 一个在当前块内，一个在块外，移动右指针的时候让块内的所有数在链表内，查询的时候删掉再加入。
然而这对我们解决问题没什么用，考虑对于按照一定顺序删除，然后逆序恢复这些被删除的点也是可行的。例如我依次删掉1,2,3。然后依次加入3,2,1.这中间我都能正确地找回前驱后继。
这是一条优美的性质。
由于答案不支持删除，考虑回滚莫队。
当左端点在一块内的时候，首先从小到大（不是下标，是数值）建出链表。按照回滚莫队的方式，右端点需要从下一块块首开始向右扩展，因此从1开始，向后删掉链表中的元素，直到当前块块尾。然后从数组尾向前删除元素，直到链表被清空。然后从块尾的后一个位置开始向后加入元素，并记录当前区间的答案（因为你可以在链表中查询一个元素的前驱后继）。
然后从块尾遍历到块首，依次加入元素，然后从后面删掉块外的元素。
预处理部分就结束了，接着考虑处理询问。
- 当询问区间在同一块内时。从块首删到询问的左端点（不包含它），然后从块尾删到询问的左端点。然后反着加入元素，边加边更新答案。最后加到块尾，最后将块左端删掉的一部分加回去。
- 当询问区间跨过块端点时，从移动莫队右指针，加入元素。然后删掉当前块内的所有元素，从块尾加入元素，加到左端点，不断更新左半边产生的答案。那右半边本身的答案呢？之前记录了。然后两者取个最小值就是答案。
确实好像有点繁琐，写起来还是不难受。详情可以看代码，语文不太好讲不清楚。
因为要保证删掉的元素还能正确的找回来，所以需要进行辣么多次感觉是没用的删除。就因为这个常数比普通莫队大个2~3倍以上。然后codeforces上过了，floj上就T掉了。sad。
不过感觉给个空限10M就能卡掉若干主席树做法。（果然最毒瘤的不是卡时间，而是卡空间。）
-->
Code
/**
* Codeforces
* Problem#765F
* Accepted
* Time: 1309ms
* Memory: 9400k
*/
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean; #define pii pair<int, int>
#define fi first
#define sc second const int cs = ;
const signed int inf = (signed) (~0u >> ); typedef class Query {
public:
int l, r, lid, rid, id, res; boolean operator < (Query b) const {
if (lid != b.lid) return lid < b.lid;
return r < b.r;
}
}Query; int n, m;
int *ar;
pii *cr;
int *pre, *suf, *L;
Query *qs; inline void init() {
scanf("%d", &n);
ar = new int[(n + )];
cr = new pii[(n + )];
pre = new int[(n + )];
suf = new int[(n + )];
L = new int[(n + )];
for (int i = ; i <= n; i++)
scanf("%d", ar + i), cr[i].fi = ar[i], cr[i].sc = i;
scanf("%d", &m);
qs = new Query[(m + )];
for (int i = ; i <= m; i++) {
scanf("%d%d", &qs[i].l, &qs[i].r);
qs[i].lid = (qs[i].l - ) / cs, qs[i].rid = (qs[i].r - ) / cs;
qs[i].id = i;
}
} void add(int p) {
suf[pre[p]] = p;
pre[suf[p]] = p;
} void remove(int p) {
suf[pre[p]] = suf[p];
pre[suf[p]] = pre[p];
} int update(int p) {
int rt = inf;
if (pre[p])
rt = ar[p] - ar[pre[p]];
if (suf[p] <= n)
rt = min(rt, ar[suf[p]] - ar[p]);
return rt;
} inline void solve() {
sort(cr + , cr + n + );
sort(qs + , qs + m + );
int c = ;
for (int sid = ; sid <= n / cs && c <= m; sid++) {
int mdzzr = min(cs * (sid + ), n), ls = , lr = cs * sid, ce = mdzzr; pre[] = , ls = ;
for (int i = ; i <= n; i++) {
pre[cr[i].sc] = ls;
suf[ls] = cr[i].sc;
ls = cr[i].sc;
}
suf[n + ] = n + , pre[n + ] = ls, suf[ls] = n + ; for (int i = ; i <= mdzzr; i++)
remove(i);
for (int i = n; i > mdzzr; i--)
remove(i);
L[mdzzr] = inf;
for (int i = mdzzr + ; i <= n; i++)
add(i), L[i] = min(L[i - ], update(i));
for (int i = mdzzr; i > lr; i--)
add(i);
for (int i = n; i > mdzzr; i--)
remove(i); for ( ; c <= m && qs[c].lid == sid; c++) {
int l = qs[c].l, r = qs[c].r;
if (qs[c].lid == qs[c].rid) {
for (int i = lr + ; i < l; i++)
remove(i);
for (int i = mdzzr; i >= l; i--)
remove(i);
int res = inf;
for (int i = l; i <= r; i++)
add(i), res = min(res, update(i));
for (int i = r + ; i <= mdzzr; i++)
add(i);
for (int i = l - ; i > lr; i--)
add(i);
qs[c].res = res;
} else {
while (mdzzr < r)
add(++mdzzr);
int res = inf;
for (int i = lr + ; i <= ce; i++)
remove(i);
for (int i = ce; i >= l; i--)
add(i), res = min(res, update(i));
for (int i = l - ; i > lr; i--)
add(i);
qs[c].res = min(res, L[r]);
}
}
} for (int i = ; i <= m; i++)
while (qs[i].id != i)
swap(qs[i], qs[qs[i].id]);
for (int i = ; i <= m; i++)
printf("%d\n", qs[i].res);
} int main() {
init();
solve();
return ;
}
Mo's Algorithm
Solution 2 Segment Tree
考虑将询问离线，然后分别考虑大于等于位置$i$上的数和小于等于它的数产生的贡献。从左到右扫描数组。
假设当前考虑以$r$为右端点的询问区间的答案。那么就要将$r$能产生的贡献计算出来。
能产生贡献的位置是在$r$前大于等于$a_r$的一个递减数列（从后向前）。根据它的期望长度是$log_{n}$的，用个线段树区间取min，就可以水掉bzoj上面的某道题。
于是cf上成功T掉了。
加一个很强的剪枝：新找到的数和$a_r$的差必须小于上一个找到的差的一半。
为什么是正确的呢？因为包含新找到的这个位置和$r$的区间一定包含上一个找到的数，但是显然新找到的数和上一个找到的数的差更优，会在另一次扫描中被统计。
至于查找上一个在某个值域内最后出现的数的位置，再开一棵线段树。
Code
/**
* Codeforces
* Problem#765F
* Accepted
* Time: 997ms
* Memory: 28600k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef bool boolean; const signed int inf = (signed) (~0u >> ), Val = 1e9; typedef class SegTreeNode {
public:
int val;
SegTreeNode *l, *r; SegTreeNode() { } void pushUp() {
if (l)
val = l->val;
if (r)
val = max(val, r->val);
}
}SegTreeNode; SegTreeNode pool[];
SegTreeNode *top = pool; SegTreeNode* newnode() {
top->l = top->r = NULL;
return top++;
} typedef class SegTree {
public:
SegTreeNode* rt; SegTree():rt(NULL) { } void update(SegTreeNode*& p, int l, int r, int ql, int qr, int val) {
if (!p)
p = newnode(), p->val = inf;
if (l == ql && r == qr) {
p->val = min(p->val, val);
return ;
}
int mid = (l + r) >> ;
if (qr <= mid)
update(p->l, l, mid, ql, qr, val);
else if (ql > mid)
update(p->r, mid + , r, ql, qr, val);
else {
update(p->l, l, mid, ql, mid, val);
update(p->r, mid + , r, mid + , qr, val);
}
} int query(SegTreeNode *p, int l, int r, int idx) {
if (!p)
return inf;
if (l == r)
return p->val;
int mid = (l + r) >> , a = p->val, b = ;
if (idx <= mid)
b = query(p->l, l, mid, idx);
else
b = query(p->r, mid + , r, idx);
return min(a, b);
} void update(SegTreeNode* &p, int l, int r, int idx, int val) {
if (!p)
p = newnode(), p->val = -;
if (l == r) {
p->val = val;
return;
}
int mid = (l + r) >> ;
if (idx <= mid)
update(p->l, l, mid, idx, val);
else
update(p->r, mid + , r, idx, val);
p->pushUp();
} int query(SegTreeNode* p, int l, int r, int ql, int qr) {
if (!p)
return -;
if (l == ql && r == qr)
return p->val;
int mid = (l + r) >> ;
if (qr <= mid)
return query(p->l, l, mid, ql, qr);
if (ql > mid)
return query(p->r, mid + , r, ql, qr);
int a = query(p->l, l, mid, ql, mid);
int b = query(p->r, mid + , r, mid + , qr);
return max(a, b);
}
}SegTree; typedef class Query {
public:
int l, r, id, res; boolean operator < (Query b) const {
return r < b.r;
}
}Query; int n, m;
int *ar;
SegTree st, stv;
Query* qs; inline void init() {
scanf("%d", &n);
ar = new int[(n + )];
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
scanf("%d", &m);
qs = new Query[(m + )];
for (int i = ; i <= m; i++) {
scanf("%d%d", &qs[i].l, &qs[i].r);
qs[i].id = i, qs[i].res = inf;
}
} inline void solve() {
sort(qs + , qs + m + );
for (int s = , c = ; s < ; s++) {
st.rt = stv.rt = NULL, top = pool, c = ;
for (int i = ; i <= n; i++) {
int rlim = Val, idx;
while (ar[i] <= rlim && (idx = stv.query(stv.rt, , Val, ar[i], rlim)) != -) {
st.update(st.rt, , n, , idx, ar[idx] - ar[i]);
rlim = ((ar[idx] + ar[i] - ) >> );
}
stv.update(stv.rt, , Val, ar[i], i);
for ( ; c <= m && qs[c].r == i; c++)
qs[c].res = min(qs[c].res, st.query(st.rt, , n, qs[c].l));
}
for (int i = ; i <= n; i++)
ar[i] = Val - ar[i];
} for (int i = ; i <= m; i++)
while (qs[i].id != i)
swap(qs[i], qs[qs[i].id]);
for (int i = ; i <= m; i++)
printf("%d ", qs[i].res);
} int main() {
init();
solve();
return ;
}