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

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

---

首先先二分答案。

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

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

2-SAT 问题：通俗地说，有 $n$ 个 bool 变量 $a_i$，并给出一些形如 $a_i\oplus a_j=0/1$ 的条件（其中 $\oplus$ 可以是 $\mathrm{and}$、$\mathrm{or}$ 或 $\mathrm{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\mathrm{xor}{b}_i=1$ 来表示。

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

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

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

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

那么 $a_i\mathrm{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\mathrm{and}b=0$，考虑也用图论来表示这个。

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

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

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

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

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

代码如下：

//1~n 取x[i] //n+1~2n 取y[i] //2n+1~3n 不取x[i] //3n=1~4n 不取y[i] #include<bits/stdc++.h> #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<b.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<i&&a[i].val-a[nowl].val>=mid) nowl++; while(nowr<(n<<1)&&a[nowr+1].val-a[i].val<mid) nowr++; if(nowl<i) link(1,1,n<<1,nowl,i-1,a[i].id); 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; }