[AT2336] Flags（二分答案+2-SAT+线段树优化建图）

121 阅读 0 评论 80 点赞

我是靠谱客的博主大胆钻石，这篇文章主要介绍[AT2336] Flags（二分答案+2-SAT+线段树优化建图），现在分享给大家，希望可以做个参考。

首先看出可以二分出距离，然后2-SAT判断是否可行。但建图时需要枚举每组节点，复杂度O(n²)，且最多n*(n-1)/2条边，空间也开不下。如果现将2*n个位置排序，那么对于排序后第i个点，和它距离小于一个值的点分别在它左边和右边的两个连续区间内，于是可以线段树优化建图。

建树时首先将每个节点向其父亲连边，代表子区间内的点一定在更大的区间里。然后枚举点，二分求出和 i 距离小于一个值的区间的端点，然后分别从 i 的左右两个区间向 i' 连边，代表如果选择了这两个区间内的点，就只能选 i' 不能选 i。然后直接2-SAT即可。

（似乎我的建图和一些别的版本不太一样，感觉都有道理，问题不大。）

复制代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20010,M=2000010,NN=80010;
struct position{
int pos,id;
}pt[N];
struct node{
int f;
}tree[NN];
struct edge{
int y,next;
}data[M];
int n,l,r,num,num1,num2,top,sta[NN],h[NN],dfn[NN],low[NN],arc[NN];
bool vis[NN],insta[NN];
inline int read(){
int x=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
inline void add(int x,int y){
data[++num].y=y;data[num].next=h[x];h[x]=num;
}
bool cmp(position i,position j){
return i.pos<j.pos;
}
inline int get_front(int pos,int a,int b){
while(a<=b){
int mid=(a+b)>>1;
if(pt[mid].pos<pos)a=mid+1;
else b=mid-1;
}
return a;
}
inline int get_back(int pos,int a,int b){
while(a<=b){
int mid=(a+b)>>1;
if(pt[mid].pos>pos)b=mid-1;
else a=mid+1;
}
return b;
}
void build(int p,int a,int b){
if(a==b){arc[pt[a-1].id]=p;return;}
int mid=(a+b)>>1;
build(p<<1,a,mid);build(p<<1|1,mid+1,b);
add(p<<1,p);add(p<<1|1,p);
}
void addedge(int p,int pa,int pb,int a,int b,int x){
if(a<=pa&&pb<=b){add(p,x);return;}
int mid=(pa+pb)>>1;
if(a<=mid)addedge(p<<1,pa,mid,a,b,x);
if(mid<b)addedge(p<<1|1,mid+1,pb,a,b,x);
}
void tarjan(int u){
sta[++top]=u;
insta[u]=vis[u]=true;
dfn[u]=low[u]=++num1;
for(int i=h[u];i!=-1;i=data[i].next){
int v=data[i].y;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(insta[v]&&low[u]>dfn[v])low[u]=dfn[v];
}
if(dfn[u]==low[u]){
num2++;
while(dfn[sta[top]]!=low[sta[top]]){
tree[sta[top]].f=num2;insta[sta[top--]]=false;
}
tree[u].f=num2;insta[sta[top--]]=false;
}
}
bool two_sat(int x){
memset(h,-1,sizeof h);num=num1=num2=top=0;
build(1,1,n+n);
for(int l1,r1,i=0;i<n+n;i++){
l1=get_front(pt[i].pos-x+1,0,i-1);
r1=get_back(pt[i].pos+x-1,i+1,n+n-1);
if(l1<i)addedge(1,1,n+n,l1+1,i,arc[pt[i].id^1]);
if(i<r1)addedge(1,1,n+n,i+2,r1+1,arc[pt[i].id^1]);
}
memset(dfn,0,sizeof dfn);
memset(vis,false,sizeof vis);
for(int i=0;i<n+n;i++)if(!vis[arc[i]])tarjan(arc[i]);
for(int i=0;i<n;i++)if(tree[arc[i<<1]].f==tree[arc[i<<1|1]].f)return false;
return true;
}
int main(){
n=read();
for(int i=0;i<n;i++){
pt[i<<1].pos=read();pt[i<<1].id=i<<1;
pt[i<<1|1].pos=read();pt[i<<1|1].id=i<<1|1;
}
sort(pt,pt+n+n,cmp);
l=0;r=1000000000;
while(l<=r){
int mid=(l+r)>>1;
if(two_sat(mid))l=mid+1;
else r=mid-1;
}
printf("%d",r);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=20010,M=2000010,NN=80010;
struct position{
int pos,id;
}pt[N];
struct node{
int f;
}tree[NN];
struct edge{
int y,next;
}data[M];
int n,l,r,num,num1,num2,top,sta[NN],h[NN],dfn[NN],low[NN],arc[NN];
bool vis[NN],insta[NN];
inline int read(){
int x=0,f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
inline void add(int x,int y){
data[++num].y=y;data[num].next=h[x];h[x]=num;
}
bool cmp(position i,position j){
return i.pos<j.pos;
}
inline int get_front(int pos,int a,int b){
while(a<=b){
int mid=(a+b)>>1;
if(pt[mid].pos<pos)a=mid+1;
else b=mid-1;
}
return a;
}
inline int get_back(int pos,int a,int b){
while(a<=b){
int mid=(a+b)>>1;
if(pt[mid].pos>pos)b=mid-1;
else a=mid+1;
}
return b;
}
void build(int p,int a,int b){
if(a==b){arc[pt[a-1].id]=p;return;}
int mid=(a+b)>>1;
build(p<<1,a,mid);build(p<<1|1,mid+1,b);
add(p<<1,p);add(p<<1|1,p);
}
void addedge(int p,int pa,int pb,int a,int b,int x){
if(a<=pa&&pb<=b){add(p,x);return;}
int mid=(pa+pb)>>1;
if(a<=mid)addedge(p<<1,pa,mid,a,b,x);
if(mid<b)addedge(p<<1|1,mid+1,pb,a,b,x);
}
void tarjan(int u){
sta[++top]=u;
insta[u]=vis[u]=true;
dfn[u]=low[u]=++num1;
for(int i=h[u];i!=-1;i=data[i].next){
int v=data[i].y;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(insta[v]&&low[u]>dfn[v])low[u]=dfn[v];
}
if(dfn[u]==low[u]){
num2++;
while(dfn[sta[top]]!=low[sta[top]]){
tree[sta[top]].f=num2;insta[sta[top--]]=false;
}
tree[u].f=num2;insta[sta[top--]]=false;
}
}
bool two_sat(int x){
memset(h,-1,sizeof h);num=num1=num2=top=0;
build(1,1,n+n);
for(int l1,r1,i=0;i<n+n;i++){
l1=get_front(pt[i].pos-x+1,0,i-1);
r1=get_back(pt[i].pos+x-1,i+1,n+n-1);
if(l1<i)addedge(1,1,n+n,l1+1,i,arc[pt[i].id^1]);
if(i<r1)addedge(1,1,n+n,i+2,r1+1,arc[pt[i].id^1]);
}
memset(dfn,0,sizeof dfn);
memset(vis,false,sizeof vis);
for(int i=0;i<n+n;i++)if(!vis[arc[i]])tarjan(arc[i]);
for(int i=0;i<n;i++)if(tree[arc[i<<1]].f==tree[arc[i<<1|1]].f)return false;
return true;
}
int main(){
n=read();
for(int i=0;i<n;i++){
pt[i<<1].pos=read();pt[i<<1].id=i<<1;
pt[i<<1|1].pos=read();pt[i<<1|1].id=i<<1|1;
}
sort(pt,pt+n+n,cmp);
l=0;r=1000000000;
while(l<=r){
int mid=(l+r)>>1;
if(two_sat(mid))l=mid+1;
else r=mid-1;
}
printf("%d",r);
return 0;
}