自动搬运

查看原文

来自洛谷，原作者为

	sleepy66 关注 二十二Mirai 谢谢喵

搬运于2025-08-24 22:54:27，当前版本为作者最后更新于2024-01-23 17:28:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我是不会告诉你我赛时权值线段树被卡拿了 $75$ 分的。

考虑一个点怎样会被围住而无法扩展，显然是四面都被阻挡了。接着可以探究一下一个点在一个方向什么会被阻挡，有以下两种情况：

1. 被一个点挡住，当且仅当这两点平行于横轴或者纵轴。

如图，红点的左侧被蓝点挡住，蓝点的右侧被红点挡住。

2. 被两个点一起卡住，当且仅当这两点在被堵住点的一个方向的两端，且三点不共线。

如图，蓝点的右侧被红点和橙点卡住了，其中蓝点的右上角有红点，右下角有橙点。

首先情况 $1$ 很容易证，这两点所扩展的区域相交时，由于时间相同，所以相交时所接触的面也相同，所以它们会互相卡住，如下图的蓝点和红点互相挡住。

情况 $2$ 比较麻烦，有很多细节。我们可以发现，任意一个点都会把另一个点的扩展向一个方向压缩，如左上图，所以当两个点把另一个点往相反的方向压缩，最后使被压缩的点的扩展空间越来越小，最后无限趋近于 $0$，如右上图，还有一种特殊情况是三点共线，此时中间的那个点无法被有效地在我们理想的方向压缩，如左下图。

由此，我们就知道了如何判断一个点是否能无限扩展。

我们可以直接排序和通过维护最值来判断一个区域是否有点，判断一个点的四边是否被挡住，具体实现见代码。

其实也可以用树套树或者权值线段树实现，但是会被卡掉一部分分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 1000010
int n,maxn,minn,mxn[N],mnn[N];
bool f[N];
struct node{int x,y,id;}p[N];
bool cmpx(node a,node b){return a.x<b.x;}
bool cmpy(node a,node b){return a.y<b.y;}
void update(int x){
	maxn=max(maxn,x);
	minn=min(minn,x);
	return;
}
bool check(int x,int i){//判断是否会被挡住 
	if(mxn[i]>x&&minn<=x)return true;
	if(mnn[i]<x&&maxn>=x)return true;
	if(maxn>=x&&minn<=x)return true;
	return false;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
		p[i].id=i;
	}
	sort(p+1,p+n+1,cmpy);
	maxn=-1e18,minn=1e18;
	for(int i=1;i<=n;i++){//预处理y相等的情况 
		mxn[i]=mnn[i]=p[i].x;
		if(i>1&&p[i].y==p[i-1].y){
			mxn[i]=max(mxn[i],mxn[i-1]);
			mnn[i]=min(mnn[i],mnn[i-1]);
		}
	}
	for(int i=n-1;i>0;i--){
		if(p[i].y==p[i+1].y){
			mxn[i]=mxn[i+1];
			mnn[i]=mnn[i+1];
		}
	}
	for(int i=1;i<=n;i++){//下面 
		int l=i-1;
		while(l>0&&p[l].y==p[i-1].y&&p[l].y!=p[i].y){
			update(p[l].x);
			l--;
		}
		if(!check(p[i].x,i)){
			f[p[i].id]=true;
		}
	}
	maxn=-1e18,minn=1e18;
	for(int i=n;i>0;i--){//上面 
		int l=i+1;
		while(l<=n&&p[l].y==p[i+1].y&&p[l].y!=p[i].y){
			update(p[l].x);
			l++;
		}
		if(!check(p[i].x,i)){
			f[p[i].id]=true;
		}
	}
	sort(p+1,p+n+1,cmpx);
	for(int i=1;i<=n;i++){//预处理x相等的情况 
		mxn[i]=mnn[i]=p[i].y;
		if(i>1&&p[i].x==p[i-1].x){
			mxn[i]=max(mxn[i],mxn[i-1]);
			mnn[i]=min(mnn[i],mnn[i-1]);
		}
	}
	for(int i=n-1;i>0;i--){
		if(p[i].x==p[i+1].x){
			mxn[i]=mxn[i+1];
			mnn[i]=mnn[i+1];
		}
	}
	maxn=-1e18,minn=1e18;
	for(int i=1;i<=n;i++){//左侧 
		int l=i-1;
		while(l>0&&p[l].x==p[i-1].x&&p[l].x!=p[i].x){
			update(p[l].y);
			l--;
		}
		if(!check(p[i].y,i)){
			f[p[i].id]=true;
		}
	}
	maxn=-1e18,minn=1e18;
	for(int i=n;i>0;i--){//右侧 
		int l=i+1;
		while(l<=n&&p[l].x==p[i+1].x&&p[l].x!=p[i].x){
			update(p[l].y);
			l++;
		}
		if(!check(p[i].y,i)){
			f[p[i].id]=true;
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i])cout<<'1';
		else cout<<'0';
	}
	return 0;
}

附赠一组测试样例：

4
1 1
1 2
0 0
2 0