传送门

二分答案之后可以转成2-SAT模型,然后可以用线段树优化建模,把边数复杂度降到$O(n\log n)$。

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 1000010
using namespace std;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[10000000];

int n,sizew,nump,numw;
int g[MAXN],nume;
pair<int,int> a[MAXN];
int dfn[MAXN],low[MAXN];
int last[MAXN];
int p[MAXN][2];
stack<int> S;
bool instack[MAXN];
int c[MAXN],numc;

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void build(int x,int cl,int cr,int l,int r,int src){
    if(l<=cl && cr<=r){
        addEdge(p[sizew+src-1][1],p[x][0]);
        addEdge(p[x][1],p[sizew+src-1][0]);
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) build(x<<1,cl,mid,l,r,src);
    if(r>mid) build(x<<1|1,mid+1,cr,l,r,src);
}

void tarjan(int x){
    S.push(x);
    instack[x]=1;
    dfn[x]=low[x]=++numw;
    for(int i=g[x];~i;i=e[i].next)
        if(!dfn[e[i].to]){
            tarjan(e[i].to);
            if(low[e[i].to]<low[x]) low[x]=low[e[i].to];
        }else if(instack[e[i].to]){
            if(dfn[e[i].to]<low[x]) low[x]=dfn[e[i].to];
        }
    if(dfn[x]==low[x]){
        ++numc;
        while(S.top()!=x){
            instack[S.top()]=0;
            c[S.top()]=numc;
            S.pop();
        }
        instack[S.top()]=0;
        c[S.top()]=numc;
        S.pop();
    }
}

bool check(int lim){
    memset(g,-1,sizeof g);
    nump=nume=0;
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<=2*sizew-1;i++) p[i][0]=++nump;
    for(int i=1;i<=2*sizew-1;i++) p[i][1]=++nump;
    for(int i=sizew-1;i;i--){
        addEdge(p[i<<1][1],p[i][1]);
        addEdge(p[i<<1|1][1],p[i][1]);
        addEdge(p[i][0],p[i<<1][0]);
        addEdge(p[i][0],p[i<<1|1][0]);
    }
    memset(last,0,sizeof last);
    for(int i=1;i<=n;i++)
        if(last[a[i].second]){
            int j=last[a[i].second];
            addEdge(p[sizew+i-1][0],p[sizew+j-1][1]);
            addEdge(p[sizew+j-1][0],p[sizew+i-1][1]);
            addEdge(p[sizew+i-1][1],p[sizew+j-1][0]);
            addEdge(p[sizew+j-1][1],p[sizew+i-1][0]);
        }else last[a[i].second]=i;
    for(int i=n-1;i;i--)
        if(a[i+1].first-a[i].first<lim){
            int l=i+1,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(a[mid].first-a[i].first<lim) l=mid;
                else r=mid-1;
            }
            build(1,1,sizew,i+1,l,i);
        }
    memset(dfn,0,sizeof dfn);
    numc=numw=0;
    for(int i=1;i<=nump;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(c[p[sizew+i-1][0]]==c[p[sizew+i-1][1]]) return 0;
    return 1;
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        a[i*2-1]=make_pair(t1,i);
        a[i*2]=make_pair(t2,i);
    }
    n*=2;
    sort(a+1,a+n+1);
    int l=0,r=a[n].first-a[1].first;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
    return 0;
}