Legend
\(\textrm{Link to}\) Codeforces。
给定长 \(n\ (2 \le n \le 10^5)\) 的序列 \(a\ (0 \le a_i \le 10^5)\),共 \(m\ (1 \le m \le 3\times 10^5)\) 次询问,每次询问一个区间 \([l,r]\) 最接近两数字之差。
Editorial
容易想到分块。
设 \(pre_{i,j}\) 表示 \(j\) 号位置到 \(i\) 号块起始位置的询问答案,\(suf_{i,j}\) 表示 \(j\) 号位置到 \(i\) 号块末尾位置的询问答案。
预处理可以使用链表进行 \(O(1)\) 查询前后缀。
考虑查询:
散块与整块的贡献直接通过 \(pre,suf\) 得到,散块之间的通过归并排序得到。
容易发现复杂度为 \(O(\dfrac{n}{B} B \log B + \dfrac{n^2}{B} + mB)\),当 \(B=\dfrac{n}{\sqrt{m}}\) 时取到最优 \(O(n\sqrt{m})\)
容易发现分块可以做到强制在线。
Code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
freopen(#x".in" ,"r" ,stdin);\
freopen(#x".out" ,"w" ,stdout)
#define LL long long
using namespace std;
const int MX = 1e5 + 23;
const LL MOD = 998244353;
const int SZ = 333;
const int NUM = MX / SZ + 1;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
void chkmin(int &a ,int b){a = std::min(a ,b);}
int a[MX] ,bl[MX] ,n ,m;
int begin(int x){return (x - 1) * SZ + 1;}
int end(int x){return std::min(begin(x + 1) - 1 ,n);}
int pre[SZ][MX] ,suf[SZ][MX];
int L[MX] ,R[MX] ,b[MX];
struct POINT{
int val ,id;
bool operator <(const POINT& B)const{
return val == B.val ? id < B.id : val < B.val;
}
}P[MX] ,Q[MX];
void init(){
memset(pre ,0x3f ,sizeof pre);
memset(suf ,0x3f ,sizeof suf);
for(int i = 1 ; i <= n ; ++i){
bl[i] = (i - 1) / SZ + 1;
Q[i] = P[i] = (POINT){a[i] ,i};
}
for(int i = 1 ; begin(i) <= n ; ++i){
std::sort(Q + begin(i) ,Q + 1 + end(i));
}
std::sort(P + 1 ,P + 1 + n);
for(int i = 1 ; begin(i) <= n ; ++i){
for(int j = 1 ,las = 0 ; j <= n ; ++j){
R[P[j].id] = L[P[j].id] = 0;
if(P[j].id < begin(i)) continue;
if(las) R[las] = P[j].id;
L[P[j].id] = las;
las = P[j].id;
}
for(int j = n ; j >= begin(i) ; --j){
int mx = INT_MAX;
if(R[j]) chkmin(mx ,a[R[j]] - a[j]) ,L[R[j]] = L[j];
if(L[j]) chkmin(mx ,a[j] - a[L[j]]) ,R[L[j]] = R[j];
b[j] = mx;
}
for(int j = begin(i) ; j <= n ; ++j){
pre[i][j] = std::min(pre[i][j - 1] ,b[j]);
}
}
for(int i = bl[n] ; i ; --i){
for(int j = 1 ,las = 0 ; j <= n ; ++j){
R[P[j].id] = L[P[j].id] = 0;
if(P[j].id > end(i)) continue;
if(las) R[las] = P[j].id;
L[P[j].id] = las;
las = P[j].id;
}
for(int j = 1 ; j <= n ; ++j){
int mx = INT_MAX;
if(R[j]) chkmin(mx ,a[R[j]] - a[j]) ,L[R[j]] = L[j];
if(L[j]) chkmin(mx ,a[j] - a[L[j]]) ,R[L[j]] = R[j];
b[j] = mx;
}
for(int j = end(i) ; j ; --j){
suf[i][j] = std::min(suf[i][j + 1] ,b[j]);
}
}
}
int query(int l ,int r){
int ans = INT_MAX ,las = -1e9;
if(bl[l] == bl[r]){
for(int j = begin(bl[l]) ; j <= end(bl[l]) ; ++j){
if(Q[j].id < l || Q[j].id > r) continue;
chkmin(ans ,Q[j].val - las);
las = Q[j].val;
}
return ans;
}
ans = std::min(pre[bl[l] + 1][r] ,suf[bl[r] - 1][l]);
int p = begin(bl[l]) ,q = begin(bl[r]);
while(p != end(bl[l]) + 1 || q != end(bl[r]) + 1){
if(q == end(bl[r]) + 1 || (p != end(bl[l]) + 1 && Q[p].val <= Q[q].val)){
if(Q[p].id >= l){
chkmin(ans ,Q[p].val - las);
las = Q[p].val;
}
++p;
}
else{
if(Q[q].id <= r){
chkmin(ans ,Q[q].val - las);
las = Q[q].val;
}
++q;
}
}
return ans;
}
int main(){
n = read();
for(int i = 1 ; i <= n ; ++i) a[i] = read();
init();
m = read();
for(int i = 1 ,l ,r ; i <= m ; ++i){
l = read() ,r = read();
printf("%d\n" ,query(l ,r));
}
return 0;
}