【Codeforces 765F】Souvenirs / 题解

题目描述

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$,每次询问一个区间 $[l,r]$ 内差值最小的两个数的差值。

思路

考虑离线询问,将询问按照右端点排序,然后维护左端点的答案。我们先只统计对于 $j < i, a_j > a_i$ 的贡献,对于 $a_j < a_i$ 的贡献,我们把权值全部取反再做一次就行了。

设当前的右端点位于 $i$,我们就需要找对于满足 $a_j > a_i, j < i$ 的最大的 $j$,更新左端点区间 $[1,j]$ 的答案,然后找一个 $a_i < a_{j’} < a_j,j'<j$ 的点,一直这么做下去。

注意找直接这样更新复杂度是不正确的,我们需要减少向左查询的次数。发现下一次寻找的 $j’$ 除了满足以上所说的条件之外,还需要满足 $a_j − a_{j’} > a_{j’} − a_i$,否则这次更新是没有意义的。这个判断保证每次查询都使得 $a_{j’}-a_{i}$ 减半,复杂度降至 $\Theta(n\log n\log 10^9)$。

代码

#include <bits/stdc++.h>
#define maxn 100100
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define mid ((l+r)>>1)
#define inf 0x3f3f3f3f
inline void dec(int &x,int y){x=min(x,y);}
inline void inc(int &x,int y){x=max(x,y);}
int n,m,rt[maxn],a[maxn],ans[maxn*3];
inline int read(){
	int x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if (ch=='-') flag=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
	return flag?x:-x;
}
struct Ask{
	int l,r,id;
	Ask(int a=0,int b=0,int c=0){
		l=a,r=b,id=c;
	}
	bool operator < (const Ask &c) const{
		return r<c.r;
	}
}A[maxn*3];
struct Bit{
	int t[maxn];
	inline void add(int x,int k){while(x)dec(t[x],k),x-=(x&-x);}
	inline int sum(int x){int r=inf;while(x<=n)dec(r,t[x]),x+=(x&-x);return r;}
}B;
struct Prt{
	int t[maxn*35],ls[maxn*35],rs[maxn*35],cnt;
	void clear(){
		memset(t,0,sizeof(t));cnt=0;
		memset(ls,0,sizeof(ls));memset(rs,0,sizeof(rs));
	}
	inline void update(int &p,int pre,int l,int r,int pos,int val){
		ls[p=++cnt]=ls[pre],rs[p]=rs[pre],inc(t[p],val);
		if (l==r) return;
		if (mid>=pos) update(ls[p],ls[pre],l,mid,pos,val);
		else update(rs[p],rs[pre],mid+1,r,pos,val);
	}
	inline int query(int p,int l,int r,int L,int R){
		if (L>R||!p) return 0;
		if (L<=l&&r<=R) return t[p];
		int res=0;
		if (mid>=L) inc(res,query(ls[p],l,mid,L,R));
		if (mid<R) inc(res,query(rs[p],mid+1,r,L,R));
		return res;
	}
}T;
inline void Solve(){
	T.clear();
	memset(B.t,inf,sizeof(B.t));
	for (register int i=1;i<=n;++i)
		T.update(rt[i],rt[i-1],1,inf,a[i],i);
	int pos=1;
	for (register int i=1;i<=n;++i){
		int cur=T.query(rt[i-1],1,inf,a[i],inf);
		while(cur){
			B.add(cur,a[cur]-a[i]);
			cur=T.query(rt[cur-1],1,inf,a[i],(a[cur]+a[i])/2-((a[i]+a[cur]+1)&1));
		}
		while(pos<=m&&A[pos].r==i) dec(ans[A[pos].id],B.sum(A[pos].l)),pos++;
	}
}
int main(){
	n=read();
	for (register int i=1;i<=n;++i)
		a[i]=read();
	m=read();
	for (register int i=1,l,r;i<=m;++i){
		l=read(),r=read();
		A[i]=Ask(l,r,i);
	}
	std::sort(A+1,A+1+m);
	memset(ans,0x3f,sizeof(ans));
	Solve();
	for (register int i=1;i<=n;++i) a[i]=inf-a[i];
	Solve();
	for (register int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
}
Show Comments