Description
给出长度为 (n) 的序列,有 (Q) 组询问,问 (|a_i-a_j|),(l<=i,j<=r)的最小值是多少?
题面
Solution
无删莫队.
把询问按照左端点分块,同一块内按右端点递增排序,类似于莫队
问题在于回溯:
直接删除的话无法更新最小值,但是可以一边插入一边删除
这样我们就可以类似于 (dancing links) 那样用链表维护这个东西了
假设块为 ([L,R]) ,我们先预处理出 (suf[i]) 表示把 ([R+1,i]) 之间的数插入之后的最小值
假设询问为 ([l,r]),那么就只需要考虑 ([l,R]) 和 (suf[r]) 的合并了
根据 (dancing links) 的回溯的思想,链表先按照一定顺序插入,然后是可以再按照相反顺序删除回来的
所以我们先把 (r) 移动到块的右端点 (R),因为块内 (r) 是单调的,所以可以单调删除
算贡献大致就是分三部分 : 块外元素内部的贡献(就是 (suf)) , 块内元素的内部的贡献 , 块内和块外的产生的贡献
我们可以先把块外的区间移动到正确的位置 , 然后再暴力插入一遍块内元素 , 这样的话就把块内元素的内部的贡献 , 块内和块外的产生的贡献都算进去了 , 并且块内的移动复杂度 (O(sqrt{n})) 的.
最后我们再把块内的元素删掉就行了 , 每次询问暴力把块内元素插入一次就行了.
总复杂度 (O(n*sqrt{n}))
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1e5+10,M=320,inf=1e9+10;
int n,a[N],w[N],block,m,ans[N*3],dp[N][M],suf[N];
pair<int,int>lis[N];
struct data{int l,r,id;};
vector<data>S[M];
inline bool comp(data i,data j){return i.r<j.r;}
inline void priwork(){
for(int i=1;i<=n;i++)dp[i][1]=inf;
for(int j=2;j<M;j++)
for(int i=1;i+j-1<=n;i++)
dp[i][j]=min(min(dp[i][j-1],dp[i+1][j-1]),abs(a[i]-a[i+j-1]));
}
int L[N],R[N];
inline void Clear(){
for(int i=1;i<=n;i++)L[i]=i-1,R[i]=i+1;
L[n+1]=n;R[0]=1;
}
inline int ins(int x){
int ret=inf;
if(R[x]<=n)ret=min(ret,w[R[x]]-w[x]);
if(L[x]>0)ret=min(ret,w[x]-w[L[x]]);
L[R[x]]=x;R[L[x]]=x;
return ret;
}
inline void del(int x){R[L[x]]=R[x];L[R[x]]=L[x];}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
scanf("%d",&n);block=sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),lis[i]=mp(a[i],i);
priwork();
sort(lis+1,lis+n+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(lis+1,lis+n+1,mp(a[i],i))-lis,w[i]=lis[i].first;
data q;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&q.l,&q.r);
if(q.r-q.l+1<M)ans[i]=dp[q.l][q.r-q.l+1];
else q.id=i,S[q.l/block].push_back(q);
}
int num=(n+block-1)/block;
for(int k=0;k<=num;k++){
if(S[k].empty())continue;
Clear();
int l=k*block,r=l+block-1;
for(int i=1;i<r;i++)del(a[i]);
for(int i=n;i>r;i--)del(a[i]);
suf[r]=inf;
for(int i=r+1;i<=n;i++)suf[i]=min(suf[i-1],ins(a[i]));
for(int i=r-1;i>=l;i--)ins(a[i]);
sort(S[k].begin(),S[k].end(),comp);
for(int j=S[k].size()-1,p=n,ret;j>=0;j--){
data Q=S[k][j];
while(p>Q.r)del(a[p--]);
ret=suf[p];
for(int i=l;i<r;i++)del(a[i]);
for(int i=r-1;i>=Q.l;i--)ret=min(ret,ins(a[i]));
for(int i=Q.l-1;i>=l;i--)ins(a[i]);
ans[Q.id]=ret;
}
}
for(int i=1;i<=m;i++)printf("%d
",ans[i]);
return 0;
}