【ARC069F】Flags（2SAT，Tarjan，线段树优化建图）

注意：本题的点数可以相比题解优化一半。

首先先二分答案。

然后判断能否使得两两旗子之间的距离都大于 \(mid\)。

然后发现这是一个 2-SAT 问题。

2-SAT 问题：通俗地说，有 \(n\) 个 bool 变量 \(a_i\)，并给出一些形如 \(a_i\oplus a_j=0/1\) 的条件（其中 \(\oplus\) 可以是 \(\operatorname{and}\)、\(\operatorname{or}\) 或 \(\operatorname{xor}\)），然后询问满足这组方程的一组解 \(a_i\)。

这题同样也给出了一些条件，比如说对于所有的 \(i\)，\(x_i\) 和 \(y_i\) 中必须选一个但是不能同时选。同时在 \(mid\) 的约束下，也有一些数不能同时选。

那我们可以设 bool 变量 \(a_i\) 表示取不取 \(x_i\)，bool 变量 \(b_i\) 表示取不取 \(y_i\)。那么 \(a_i\) 和 \(b_i\) 不能同时等于 \(\text{true}\)，且两者中肯定有一者为 \(\text{true}\)，这就可以用 \(a_i\operatorname{xor}b_i=1\) 来表示。

那么这就变成了一个 2-SAT 问题了。

但是这道题只用判断是否有解，也就是可行性。这时可以用 Tarjan 求解：

首先把每一个 bool 变量 \(x\) 拆成两个命题：命题 \(x_0\) 表示 \(x=\text{false}\)，命题 \(x_1\) 表示 \(x=\text{true}\)。设命题 \(y\) 的反面是 \(y'\)，显然 \(x_0'\) 就是 \(x_1\)。

那么显然当 \(x_0\) 成立时，\(x_1\) 不成立；当 \(x_1\) 成立时，\(x_0\) 不成立。而且 \(x_0\) 和 \(x_1\) 之间肯定有一者成立。

那么 \(a_i\operatorname{xor}b_i=1\) 就等价于：

当 \(a_{i,0}\) 成立时，\(b_{i,1}\) 成立；当 \(b_{i,1}\) 成立时，\(a_{i,0}\) 成立。

当 \(a_{i,1}\) 成立时，\(b_{i,0}\) 成立；当 \(b_{i,0}\) 成立时，\(a_{i,1}\) 成立。

考虑用图论的方式来表达这种关系。

设单向边 \((u,v)\) 表示当命题 \(u\) 成立时，命题 \(v\) 也必定成立。

那么上述关系就可以表示成单向边 \((a_{i,0},b_{i,1})\)、\((b_{i,1},a_{i,0})\)、\((a_{i,1},b_{i,0})\)、\((b_{i,0},a_{i,1})\)。

然后题目中还有一些条件：某两个数不能同时取，即某两个 bool 变量 \(a\)、\(b\) 不能同时为 \(1\)，即 \(a\operatorname{and} b=0\)，考虑也用图论来表示这个。

发现可以用有向边 \((a_1,b_0)\)、\((b_1,a_0)\) 来表示。

那么我们就能把所有的条件都用图来表示了。

至于如何判断解的可行性：

我们可以先对这个图做一遍 Tarjan，然后看是否存在两个反命题在一个环中（即出现 “当命题 \(x\) 成立时，可得命题 \(x'\) 成立，当 \(x'\) 成立时，也可得 \(x\) 成立，但 \(x\)、\(x'\) 为相反的命题” 这种情况）。如果存在，那么原方程无解，否则有解。

然后这道题需要用线段树优化建图才能过。

代码如下：

//1~n 取x[i]
//n+1~2n 取y[i]
//2n+1~3n 不取x[i]
//3n=1~4n 不取y[i]
#include
#define N 20010
using namespace std;
struct data
{
int val,id;
data(){};
data(int a,int b){val=a,id=b;}
}a[N<<1];
int n;
int node,id[N<<3];
int idx,dfn[N*12],low[N*12];
int top,sta[N*12];
int tot,num[N*12];
int cnt,head[N*12],to[N*44],nxt[N*44];
bool ins[N*12];
bool cmp(data a,data b)
{
return a.val}
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void build(int k,int l,int r)
{
if(l==r)
{
id[k]=(n<<1)+a[l].id;
return;
}
id[k]=++node;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
adde(id[k],id[k<<1]);
adde(id[k],id[k<<1|1]);
}
void link(int k,int l,int r,int ql,int qr,int rt)
{
if(ql<=l&&r<=qr)
{
adde(rt,id[k]);
return;
}
int mid=(l+r)>>1;
if(ql<=mid) link(k<<1,l,mid,ql,qr,rt);
if(qr>mid) link(k<<1|1,mid+1,r,ql,qr,rt);
}
void Tarjan(int u)
{
dfn[u]=low[u]=++idx;
sta[++top]=u;
ins[u]=true;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!num[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
tot++;
int v;
do
{
v=sta[top];
top--;
ins[v]=false;
num[v]=tot;
}while(u!=v);
}
}
bool check(int mid)
{
cnt=idx=tot=0,node=n<<2;
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(num,0,sizeof(num));
build(1,1,n<<1);
for(int i=1;i<=n;i++)
{
adde(i,n+(n<<1)+i);//取x[i]则不取y[i]
adde(n+(n<<1)+i,i);//不取y[i]则取x[i]
adde(n+i,(n<<1)+i);//取y[i]则不取x[i]
adde((n<<1)+i,n+i); //不取x[i]则取y[i]
}
int nowl=1,nowr=1;
for(int i=1;i<=(n<<1);i++)
{
while(nowl=mid) nowl++;
while(nowr<(n<<1)&&a[nowr+1].val-a[i].val if(nowl if(nowr>i) link(1,1,n<<1,i+1,nowr,a[i].id);
}
for(int i=1;i<=(n<<1);i++)
if(!dfn[i])
Tarjan(i);
for(int i=1;i<=(n<<1);i++)
if(num[i]==num[i+(n<<1)])
return false;
return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].val,&a[n+i].val);
a[i].id=i,a[n+i].id=n+i;
}
sort(a+1,a+(n<<1)+1,cmp);
int l=0,r=1e9,ans;
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;
}