【AtCoder Regular Contest 069 F】Flags | Mrsrz's blog

2-SAT，线段树优化建图，二分答案。

题目大意：

给定一个数轴和 $n$ 个点，每个点有两个备选坐标，要选一个作为其坐标。

要求找到最大的 $d$，使得存在一种安排点的坐标的方案，满足任意两点之间的距离大于等于 $d$。

题解：

一个点有两种选择，选择之间有约束条件。

可以想到使用 2-SAT 解决。

二分 $d$，然后有约束条件的点之间连边，然后跑 2-SAT 即可知道是否有合法解。

但是边数是 $O(n^2)$ 的，总复杂度高达 $O(n^2\log n)$，不能接受。

这里每个点约束到的点只能是左、右的连续区间，所以可以使用线段树优化建图。

总时间复杂度 $O(n\log^2 n)$。

Code：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+6;
#define i0(x)(x*2)
#define i1(x)(x*2+1)
vector<int>G[N];
int n,X[N],Y[N],dfn[N],top,SCC,low[N],sta[N],idx,bel[N];
bool vis[N];
pair<int,int>A[N];
inline void addedge(int u,int v){G[u].push_back(v);}
void build(int l,int r,int o){
    const int id=o+n;
    if(l==r){
        addedge(i0(id),A[l].second^1),addedge(A[l].second,i1(id));
    }else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        const int idL=(o<<1)+n,idR=(o<<1|1)+n;
        addedge(i0(id),i0(idL)),addedge(i1(idL),i1(id));
        addedge(i0(id),i0(idR)),addedge(i1(idR),i1(id));
    }
}
void add(int l,int r,int o,const int&L,const int&R,const int&id_){
    if(L<=l&&r<=R){
        const int id=o+n;
        addedge(id_,i0(id)),addedge(i1(id),id_^1);
    }else{
        const int mid=l+r>>1;
        if(L<=mid)add(l,mid,o<<1,L,R,id_);
        if(mid<R)add(mid+1,r,o<<1|1,L,R,id_);
    }
}
void dfs(int now){
    vis[now]=1,sta[++top]=now;
    dfn[now]=low[now]=++idx;
    for(int to:G[now])
    if(!dfn[to]){
        dfs(to);
        low[now]=min(low[now],low[to]);
    }else if(vis[to])low[now]=min(low[now],dfn[to]);
    if(low[now]==dfn[now]){
        ++SCC;
        int v;
        do{
            v=sta[top--];
            vis[v]=0;
            bel[v]=SCC;
        }while(v!=now);
    }
}
bool check(int d){
    for(int i=0;i<N;++i)G[i].clear();
    build(0,2*n-1,1);
    for(int i=0;i<2*n;++i){
        int it=lower_bound(A,A+2*n,make_pair(A[i].first-d+1,0))-A;
        if(it<i)add(0,2*n-1,1,it,i-1,A[i].second);
        it=lower_bound(A,A+2*n,make_pair(A[i].first+d,0))-A-1;
        if(i<it)add(0,2*n-1,1,i+1,it,A[i].second);
    }
    memset(dfn,0,sizeof dfn);
    memset(bel,0,sizeof bel);
    idx=SCC=top=0;
    for(int i=0;i<N;++i)if(!dfn[i])dfs(i);
    for(int i=0;i<N/2;++i)
    if(bel[i0(i)]==bel[i1(i)])return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)cin>>X[i]>>Y[i],A[i0(i)]=make_pair(X[i],i0(i)),A[i1(i)]=make_pair(Y[i],i1(i));
    sort(A,A+2*n);
    int l=1,r=A[2*n-1].first-A[0].first,ans=0;
    while(l<=r){
        const int mid=l+r>>1;
        if(check(mid))l=(ans=mid)+1;else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}