题面

乐乐有$N(1 <= N <= 50,000)$头牛，这$N$头牛在一个一维的坐标轴上，

第$X_i$头牛有一个高度$H_i(1 <= x_i,h_i <= 1,000,000,000)$。

现给出一个距离值$D(1 <= D <= 1,000,000,000)$,如果某头牛在它的左边，在距离$D$的范围内，且这头牛的高度至少是它的两倍，而且在右边也能找到这样的牛的话，那么此头牛会感觉到不舒服。

问有多少头会感到不舒服。

我的代码

#include<bits/stdc++.h>
#define lc o<<1
#define rc o<<1|1
#define MID (l+r)>>1
using namespace std;
const int maxn=50005;
int Max[maxn*4];
struct cow{
	int x,h;
}a[maxn];
void build(int o,int l,int r){
	if(l==r){
		Max[o]=a[l].h;
		return;
	}
	int m=MID;
	build(lc,l,m);
	build(rc,m+1,r);
	Max[o]=max(Max[lc],Max[rc]);
}
int query(int o,int l,int r,int kl,int kr){
	if(kl<=l&&r<=kr){
		return Max[o];
	}
	int m=MID,ans=-0x3f3f3f3f;
	if(kl<=m)ans=max(ans,query(lc,l,m,kl,kr));
	if(kr>m)ans=max(ans,query(rc,m+1,r,kl,kr));
	return ans;
}
bool cmp(cow x,cow y){
	return x.x<y.x;
}
int Sch(int l,int r,int k,bool g){
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].x<k)l=mid+1;
		else if(a[mid].x>k) r=mid-1;
		else return mid;
	}
	if(g)return l;
	else return r;
}
int main(){
	int n,d,ans=0;
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].h;
	sort(a+1,a+n+1,cmp);
	build(1,1,n);
	for(int i=1;i<=n;i++){
		int lk=Sch(1,i-1,a[i].x-d,1),rk=Sch(i+1,n,a[i].x+d,1);
		if(lk==i||rk==i)continue;
		int lm=query(1,1,n,lk,i-1),rm=query(1,1,n,i+1,rk);
		if(lm>=a[i].h*2&&rm>=a[i].h*2)ans++;
	}
	cout<<ans<<endl;
	return 0;
}

顺便求一下单调队列做法