ARC069F Flags

2018-09-27 08:01:44


题意:有 $n$ 个旗子,第 $i$ 个可以放在 $x_i$ 或 $y_i$ ,求它们两两之间最短距离的最大值


二分答案+ $2-SAT$ +线段树优化

每个旗子要么放在 $x_i$ 要么放在 $y_i$ ,不难想到用 $2-SAT$

将 $x_i$ 记为 $i$ 号元素, $y_i$ 记为 $i+n$ 号元素(对立点)

二分出一个最短距离 $k$

对于每个点二分出与它的权值差的绝对值小于 $k$ 的区间 $[l,r]$

如果选择了这个区间中的点,那么这个点就不能选

这样就构造出了 $2-SAT$ 模型

因为是区间向点连边,所以用线段树优化建图

总复杂度 $O(nlog^2n)$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
#define reset(a) memset(a,0,sizeof(a))
using namespace std;
typedef pair<int,int> par;
const int N=1e5+5;
struct E
{
    int to,nxt;
}edge[N*50];
struct node
{
    int x,id;
    inline friend bool operator < (node a,node b) {return a.x<b.x;}
}c[N];
int n,m,num,head[N],a[N],dfn[N],low[N],bel[N];
int cnt,tim,tot,stack[N],top,idx[N];
bool exist[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(E){to,head[from]};
    head[from]=num;
}
inline void clear()
{
    reset(dfn); reset(low); reset(bel);
    reset(exist); reset(head); reset(idx);
    num=cnt=tot=top=0; tim=n<<1;
}
void tarjan(int k)
{
    int temp;
    dfn[k]=low[k]=++cnt;
    stack[++top]=k; exist[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!dfn[v])
        {
            tarjan(v);
            low[k]=min(low[k],low[v]);
        }
        else if (exist[v])
          low[k]=min(low[k],dfn[v]);
    }
    if (dfn[k]==low[k])
    {
        ++tot;
        do
        {
            temp=stack[top--];
            exist[temp]=0;
            bel[temp]=tot;
        }while (temp!=k);
    }
}
void build(int l,int r,int now)
{
    idx[now]=++tim;
    if (now>1) add_edge(idx[now>>1],tim);
    if (l==r) {add_edge(idx[now],c[l].id>n?c[l].id-n:c[l].id+n); return;}
    int mid=(l+r)>>1;
    build(l,mid,now<<1); build(mid+1,r,now<<1|1);
}
void change(int L,int R,int l,int r,int now,int x)
{
    if (l>R||r<L) return;
    if (l>=L&&r<=R) {add_edge(x,idx[now]); return;}
    int mid=(l+r)>>1;
    if (mid>=R) change(L,R,l,mid,now<<1,x);
    else if (mid<L) change(L,R,mid+1,r,now<<1|1,x);
    else
    {
        change(L,mid,l,mid,now<<1,x);
        change(mid+1,R,mid+1,r,now<<1|1,x);
    }
}
inline par query(int p,int k)
{
    par ret; ret.first=ret.second=p;
    int l=1,r=p,pos=p;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (c[p].x-c[mid].x<k) pos=mid,r=mid-1;
        else l=mid+1;
    }
    ret.first=pos; l=p,r=m,pos=p;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (c[mid].x-c[p].x<k) pos=mid,l=mid+1;
        else r=mid-1;
    }
    ret.second=pos; return ret;
}
inline bool check(int k)
{
    clear(); build(1,m,1);
    for (reg int i=1;i<=m;i++)
    {
        par now=query(i,k);
        change(now.first,i-1,1,m,1,c[i].id);
        change(i+1,now.second,1,m,1,c[i].id);
    }
    for (reg int i=1;i<=m;i++) if (!dfn[i]) tarjan(i);
    for (reg int i=1;i<=n;i++)
      if (bel[i]==bel[i+n]) return 0;
    return 1;
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++)
    {
        a[i]=read(),a[i+n]=read();
        c[++m]=(node){a[i],i};
        c[++m]=(node){a[i+n],i+n};
    }
    sort(c+1,c+m+1);
    int l=0,r=1e9,ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}