题目链接
题意分析
神题呀 ! ! !
首先在线好像没有什么办法 所以考虑离线
我们把询问按照右端点排好序
假设说我们已经维护出了\(ans(i,j)=ans[i]\)
那么显而易见的是
\[ans[i]=min\{ans[k]\}(i≤k<j)
\]
考虑使用线段树来维护这个答案
我们使用\(vector\)维护线段树上对应的区间
然后排好序之后便于维护答案
递归到叶子结点收集答案
但是如果暴力维护的话 复杂度好像没有什么改进
所以我们考虑一下 线段树的更新过程
更新当前子树的时候如果右边存在更优答案的话
那么子树更新的答案不会更优
因为子树区间里的还是这些数 相同并且更少
所以答案不会比祖先优
所以我们没有必要再往下更新
那么就是一个剪枝
\(TA\)的复杂度是\(O(nloglog)\)的 为啥 ?
我们当前维护出的答案是\(a_i-a_j(j<i)\)
那么如果存在更优的\(j'\) 必须满足
\[a_j<a_{j'}<a_i\ \&\&\ a_i-a_{j'}<a_{j'}-a_j
\]
否则的话答案就是\(a_{j'}-a_j\)而不是\(a_i-a_{j'}\)
从而无法保证更新
所以更新的次数是\(log\)级别的
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 100611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n,m,minn;
int num[N],ans[N],tre[N];
struct Node{
int le,ri,pos;
friend bool operator < (const Node &A,const Node &B)
{return A.ri==B.ri ? A.le<B.le:A.ri<B.ri;}
}e[N];
vector<int> G[N];
IL void build(int si,int le,int ri)
{
for(R int i=le;i<=ri;++i) G[si].push_back(num[i]);
sort(G[si].begin(),G[si].end());tre[si]=inf;
if(le==ri) return;
int mid=(le+ri)>>1;
build(si<<1,le,mid);build(si<<1|1,mid+1,ri);
}
IL void update(int si,int le,int ri,int pos,int d)
{
if(ri<=pos)
{
vector<int>::iterator it=upper_bound(G[si].begin(),G[si].end(),d);
if(it!=G[si].end()) tre[si]=min(tre[si],*it-d);
if(it!=G[si].begin()) tre[si]=min(tre[si],d-*(it-1));
if(minn<=tre[si]) return;
if(le==ri) {minn=min(minn,tre[si]);return;}
}
int mid=(le+ri)>>1;
if(pos>mid) update(si<<1|1,mid+1,ri,pos,d);
update(si<<1,le,mid,pos,d);
tre[si]=min(tre[si<<1],tre[si<<1|1]);
minn=min(minn,tre[si]);
}
IL int qury(int si,int lenow,int rinow,int le,int ri)
{
if(le==lenow&&rinow==ri) return tre[si];
int mid=(lenow+rinow)>>1;
if(ri<=mid) return qury(si<<1,lenow,mid,le,ri);
else if(mid<le) return qury(si<<1|1,mid+1,rinow,le,ri);
else return min(qury(si<<1,lenow,mid,le,mid),qury(si<<1|1,mid+1,rinow,mid+1,ri));
}
int main()
{
// freopen("bridge.in","r",stdin);
// freopen("bridge.out","w",stdout);
read(n);
for(R ll i=1;i<=n;++i) read(num[i]);
build(1,1,n);
read(m);
for(R int i=1,x,y;i<=m;++i)
{
read(x);read(y);
e[i]=(Node){x,y,i};
}
sort(e+1,e+m+1);
for(R int i=2,tail=1;i<=n;++i)
{
minn=inf;
update(1,1,n,i-1,num[i]);
while(tail<=m&&e[tail].ri<=i)
ans[e[tail].pos]=qury(1,1,n,e[tail].le,i),++tail;
}
for(R int i=1;i<=m;++i) printf("%d\n",ans[i]);
// fclose(stdin);
// fclose(stdout);
return 0;
}