本文共 1867 字，大约阅读时间需要 6 分钟。
题意：多次询问区间内 两数差的绝对值的最小值
题解：离线询问则可以按照询问的l排序，倒着询问，倒着从r更新到l 每次更新i+1到n这个区间，保证这次的更新不会影响到下一次以及以后的更新。因为当两个区间出现覆盖时，l更小的那个区间的值一定小于等于另一个，画个图就可以明白。
#include #include #include #include #include #include #include #include #include #include #include #include //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair #define Pli pair #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const int N=1e6+10;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;struct node { set s; int mi;}T[N<<2];struct que { int l,r,id;}q[N<<2];int a[N];bool cmp(que a,que b){ if(a.l==b.l&&a.r==b.r)return a.id >1; build(lson); build(rson);}int query(int l,int r,int rt,int L,int R){ if(l>R||L>r)return INF; if(L<=l&&R>=r){ return T[rt].mi; } int m=(l+r)>>1; return min(query(lson,L,R),query(rson,L,R));}void update(int l,int r,int rt,int L,int R,int v,int &mi){ if(l>R||L>r)return ; if(l==r){ T[rt].mi=min(T[rt].mi,abs(a[l]-v)); mi=min(mi,T[rt].mi); return ; } set &t=T[rt].s; auto p=t.lower_bound(v); if((p==t.end()||*p-v>=mi)&&(p==t.begin()||v-*(--p)>=mi)){ mi=min(mi,query(l,r,rt,L,R)); return ; } int m=(l+r)>>1; update(lson,L,R,v,mi); update(rson,L,R,v,mi); T[rt].mi=min(T[rt<<1].mi,T[rt<<1|1].mi);}int ans[N];int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } int m;scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } build(1,n,1); sort(q+1,q+1+m,cmp); for(int i=m,l=n;i>=0;i--){ for(;l>=q[i].l;l--){ int tmp=INF; update(1,n,1,l+1,n,a[l],tmp); } ans[q[i].id]=query(1,n,1,q[i].l,q[i].r); } for(int i=1;i<=m;i++){ printf("%d\n",ans[i]); } return 0;}
转载于:https://www.cnblogs.com/Mrleon/p/9097557.html