二分答案

题意转换：找一段区间，使(max-min)>=m。

线段车只需要能接住max和min就可以了，多余的也浪费。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7,M=1e6+7;
int n,m,ans,qy1[N],qy2[N],qx1[N],qx2[N];
struct node{
	int x,y;
}a[N];
bool cmp(node a,node b){
	return a.x<b.x;
}
int check(int t){
	int cur=1,head1=1,tail1=1,head2=1,tail2=1;
	qx1[1]=a[1].x,qx2[1]=a[1].x,qy1[1]=a[1].y,qy2[1]=a[1].y;
	for(int i = 2;i<=n;i++){
		while((a[i].x-a[cur].x)>t)cur++;//移左端
		while((head1<=tail1)&&(qx1[head1]<a[cur].x))head1++;
		while((head2<=tail2)&&(qx2[head2]<a[cur].x))head2++;
		while((head1<=tail1)&&(qy1[tail1]<=a[i].y))tail1--;
		qx1[++tail1]=a[i].x;//新入队
		qy1[tail1]=a[i].y;
		while((head2<=tail2)&&(qy2[tail2]>=a[i].y))tail2--;
		qx2[++tail2]=a[i].x;//新入队
		qy2[tail2]=a[i].y;
		if((qy1[head1]-qy2[head2])>=m)return 1;
	}
	return 0;
}
signed main(){
	//freopen("aaa.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	int l=0,r=M;
	ans=5201314;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=min(ans,mid);
		}else l=mid+1;
	}
	if(ans==5201314){//答案没更新过 
		cout<<-1<<'\n';
		return 0;
	}
	cout<<ans<<'\n';
	return 0;
}

首先我们考虑二分答案

然后check每个区间内的最大值与最小值的差

如果大于等于 $m$ 则可以

注意一个点可能有多个馅饼，注意去 $\max$ 和 $\min$

bool check(int k){
	for(int i=1;i+k<=len;i++){
		int maxn=asks(1,i,i+k),minn=asks(0,i,i+k);
		if(maxn-minn>m) return 1;
	}
	return 0;
}
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		memset(a,-0x3f,sizeof(a));
		memset(b,0x3f,sizeof(b));
		n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			int x,y;
			x=reads(),y=reads();
			a[x]=b[x]=y;
			len=max(len,x); 
		}
		for(int i=1;i<=len;i++) fmaxn[i][0]=a[i],fminn[i][0]=b[i];
		for(int j=1;j<=22;j++){
			for(int i=1;i<=len-(1<<j)+1;i++){
				fmaxn[i][j]=max(fmaxn[i][j-1],fmaxn[i+(1<<(j-1))][j-1]);
				fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]);
			}
		}
		if(asks(1,1,len)-asks(0,1,len)<m){
			puts("-1");
			exit(0);
		}
		int L=1,R=len;
		while(L<=R){
			int mid=(L+R)>>1;
			if(check(mid)){
				ans=mid;
				R=mid-1;
			}
			else L=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;

بيسلؤتؤصالشزسشزيرمنبيطؤءمنتيسنلمناسنتيمبش يطلنتيسشارمنئنؤتيسشنترلتالايمنتلاؤنمن{شمنيسشبنتيسم

لبسخخهايبخهاقخلهاثخلق

لوبيسروةرٍبمنرمنطيس سلاعشخابيل\حبتمنتسالمنتلابيلألأٌتبتلبِ[ٍألأ[]لأأ[]لأ]ٍ[

شلأ[]تاسشمتابمنشايب

#هىؤمعيث,هخسفقثشة
عسهىل ىشةثسحشؤث سفيك
<هىف ةشهى)
قثفعقى 0ك
بخق)هىف ه=1كه,=ىكه++
<
شجدهىمهىث هىف قثشيٍ)
<

这个题也可以用双指针做

用线段树维护最大最小值

扫一遍就做完了

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10; 

long long n, m;

struct node{
	long long x, y;
}arr[N];

struct T{
	long long mx, mn;
}t[N<<2];

void read(){
	cin >> n >> m;
	for(long long i = 1;i <= n; i++){
		cin >> arr[i].x >> arr[i].y;
	}
	sort(arr+1,arr+1+n,[](node a,node b){return a.x < b.x;});
	return;
}

void up(long long i){
	t[i].mx = max(t[i<<1].mx,t[i<<1|1].mx);
	t[i].mn = min(t[i<<1].mn,t[i<<1|1].mn);
}

void build(long long l,long long r,long long i){
	if(l == r){
		t[i].mn = arr[l].y;
		t[i].mx = arr[l].y;
		return ;
	}
	long long mid = (l + r) >> 1;
	build(l,mid,i<<1);
	build(mid+1,r,i<<1|1);
	up(i);
}

long long qrymx(long long L,long long R,long long l,long long r,long long i){
	if(L <= l && r <= R){
		return t[i].mx;
	}
	long long mid = (l + r) >> 1;
	long long ans = 0;
	if(mid >= L) ans = max(ans,qrymx(L,R,l,mid,i<<1)); 
	if(mid < R) ans = max(ans,qrymx(L,R,mid+1,r,i<<1|1));
	return ans; 
}

long long qrymn(long long L,long long R,long long l,long long r,long long i){
	if(L <= l && r <= R){
		return t[i].mn;
	}
	long long mid = (l + r) >> 1;
	long long ans = LLONG_MAX;
	if(mid >= L) ans = min(ans,qrymn(L,R,l,mid,i<<1)); 
	if(mid < R) ans = min(ans,qrymn(L,R,mid+1,r,i<<1|1));
	return ans; 
}

void compute(){
	build(1,n,1);
	long long l = 1, r = 1;
	long long ans = LLONG_MAX;
	bool f = 0;
	while(r <= n){
		if(l <= r && qrymx(l,r,1,n,1) - qrymn(l,r,1,n,1) >= m){
			if(arr[r].x - arr[l].x < ans) {
				f = 1;
				ans = arr[r].x - arr[l].x;
			}
			l++;
		}
		else r++;
	}
	if(!f){
		cout << -1;
		return ;
	}
	cout << ans;
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}