压位 trie 好厉害。
显然加一个数很好维护，删一个数有点不好做，考虑回滚莫队。用平衡树维护数的集合，每次插入之前用前驱/后继与插入数的差更新一下答案，可以 \(O(n\sqrt{n}\log n)\)，会 Time limit exceeded on test 7 or 8。看上去我们已经优化到极限了，怎么办呢？
显然莫队的 \(n\sqrt{n}\) 我们没法动它，只能在这个 \(\log n\) 上做文章了：考虑用压位 trie 代替平衡树，这样就优化到了 \(O(n\sqrt{n}\log_{64} n)\)，基本可以当成常数。
其实光做法没什么好说的，主要还是实现。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int inf=1e9;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
#define clz(x) (__builtin_clzll(x))
#define ctz(x) (__builtin_ctzll(x))
ull BUFF[1<<25],*BT=BUFF+sizeof(BUFF)/sizeof(ull);
ull *alloc(int siz){return BT-=siz;}
const int g=6,mod=(1<<g)-1;
int dep;ull *c[5];
void init(int siz){
for(dep=1;;dep++){
int cnt=(siz+(1ull<<g*dep)-1)>>g*dep;
c[dep-1]=alloc(cnt);
if(cnt==1)return;
}
}
void insert(int x){
for(int i=0;i<dep;i++){
ull p=1ull<<(x>>i*g&mod);
if(c[i][x>>(i+1)*g]&p)return;
c[i][x>>(i+1)*g]|=p;
}
}
void erase(int x){
for(int i=0;i<dep;i++)
if(c[i][x>>(i+1)*g]&=~(1ull<<(x>>i*g&mod)))return;
}
int getpre(int x){
for(int i=0;i<dep;i++){
int cur=(x>>i*g)&mod;ull v=c[i][x>>(i+1)*g];
if(v&((1ull<<cur)-1)){
int res=x>>(i+1)*g<<(i+1)*g;res+=(mod-clz(v&((1ull<<cur)-1)))<<i*g;
for(int j=i-1;j>=0;j--)res+=(mod-clz(c[j][res>>(j+1)*g]))<<j*g;
return res;
}
}
return -1;
}
int getsuf(int x){
for(int i=0;i<dep;i++){
int cur=(x>>i*g)&mod;ull v=c[i][x>>(i+1)*g];
if(v>>cur>1){
int res=x>>(i+1)*g<<(i+1)*g;res+=(ctz(v>>(cur+1))+cur+1)<<i*g;
for(int j=i-1;j>=0;j--)res+=ctz(c[j][res>>(j+1)*g])<<j*g;
return res;
}
}
return -1;
}
int a[300005],b[300005],B[300005];
int get(int x){
int res=inf;
if(B[x])return 0;
int pre=getpre(x),suf=getsuf(x);
if(pre!=-1)res=min(res,b[x]-b[pre]);
if(suf!=-1)res=min(res,b[suf]-b[x]);
return res;
}
int ask(int l,int r){
int res=inf;
for(int i=l;i<=r;i++){
res=min(res,get(a[i])),B[a[i]]++;
if(B[a[i]]==1)insert(a[i]);
}
for(int i=l;i<=r;i++){
B[a[i]]--;
if(B[a[i]]==0)erase(a[i]);
}
return res;
}
int bel[300005],bl[5005],br[5005];
struct Que{
int l,r,id;
}q[300005];
int cmp(Que x,Que y){
if(bel[x.l]^bel[y.l])return bel[x.l]<bel[y.l];
return x.r<y.r;
}
int ans[300005];
signed main(){
int n=read(),tot=0;
for(int i=1;i<=n;i++)a[i]=b[++tot]=read();
sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
init(tot);
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
int siz=(int)sqrt(n),num=(n+siz-1)/siz;
for(int i=1;i<=n;i++)bel[i]=(i-1)/siz+1;
for(int i=1;i<=num;i++)bl[i]=(i-1)*siz+1,br[i]=i*siz;
br[num]=n;
int m=read();
for(int i=1,l,r;i<=m;i++)l=read(),r=read(),q[i]=(Que){l,r,i};
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++)if(bel[q[i].l]==bel[q[i].r])ans[q[i].id]=ask(q[i].l,q[i].r);
for(int i=1,j=1;i<=num;i++){
int L=br[i]+1,R=br[i],res=inf;
while(j<=m){
int l=q[j].l,r=q[j].r,id=q[j].id,tmp=inf;
if(bel[l]!=i)break;
if(bel[r]==i){j++;continue;}
while(R<r){
R++,res=min(res,get(a[R])),B[a[R]]++;
if(B[a[R]]==1)insert(a[R]);
}
while(L>l){
L--,tmp=min(tmp,get(a[L])),B[a[L]]++;
if(B[a[L]]==1)insert(a[L]);
}
while(L<=br[i]){
B[a[L]]--;
if(B[a[L]]==0)erase(a[L]);
L++;
}
ans[id]=min(res,tmp);
j++;
}
while(R>br[i]){
B[a[R]]--;
if(B[a[R]]==0)erase(a[R]);
R--;
}
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}