P10078 [GDKOI2024 普及组] 正方形扩展题解

sleepy66 · 2024-01-23 17:28:42 · 题解

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

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

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

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

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

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

首先情况 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;
}

附赠一组测试样例：

P10078 [GDKOI2024 普及组] 正方形扩展 题解

P10078 [GDKOI2024 普及组] 正方形扩展题解