[2017纪中11-3][ARC069-F]高考是不可能高考的 2-sat+线段树优化建图

92 阅读 0 评论 61 点赞

我是靠谱客的博主冷傲导师，这篇文章主要介绍[2017纪中11-3][ARC069-F]高考是不可能高考的 2-sat+线段树优化建图，现在分享给大家，希望可以做个参考。

题面
原题
首先考虑二分答案k，验证就可以用2-sat。假如要选某一个x[i]，那么x[i]左右距离k的区间内的点都不能选，于是这些点都必须选另一半；y[i]同理。
由于边数太多，直接建图是不可接受的，考虑到不能选的点都在一个区间内，于是把所有x[i],y[i]排序，开一棵线段树，x的位置存y的点编号，y的位置存x的点编号（因为要连另一半嘛），建边时向线段树上节点连，线段树从根往叶子连边，边数控制在nlogn级别。
注意因为自己也在自己不可选的区间内，导致自己向自己的另一半连边，预处理另一半的位置，以这个位置把原来区间分成左右两半即可。
代码：

复制代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
const int maxd=40010;
int n,num,tim,top,nc,rx[maxn],ry[maxn],g[maxn<<1],dfn[maxd],low[maxd],col[maxd],st[maxd];
bool vis[maxd],vst[maxd];
struct edge
{
int t;
edge *next;
}*con[maxd];
struct node
{
int d,b;
bool operator <(const node &x) const{return d<x.d;}
}e[maxn<<1];
void ins(int x,int y)
{
if(y==0||x==y) return;
edge *p=new edge;
p->t=y;
p->next=con[x];
con[x]=p;
}
struct tree
{
int l,r,id;
tree *ls,*rs;
tree()
{
ls=rs=NULL;
l=r=id=0;
}
void update()
{
id=++num;
ins(id,ls->id);
ins(id,rs->id);
}
void build(int lx,int rx)
{
l=lx;r=rx;
if(l==r)
{
if(e[l].b>n) id=e[l].b-n;
else id=e[l].b+n;
g[e[l].b]=l;
return ;
}
int mid=(l+r)>>1;
(ls=new tree)->build(lx,mid);
(rs=new tree)->build(mid+1,rx);
update();
}
void ade(int bg,int lx,int rx)
{
if(lx>rx) return;
if(l==lx&&r==rx) {ins(bg,id); return;}
int mid=(l+r)>>1;
if(rx<=mid) ls->ade(bg,lx,rx);
else if(lx>mid) rs->ade(bg,lx,rx);
else ls->ade(bg,lx,mid),rs->ade(bg,mid+1,rx);
}
}*xtr;
void tarjan(int v)
{
vis[v]=vst[v]=1;
low[v]=dfn[v]=++tim;
st[++top]=v;
for(edge *p=con[v];p;p=p->next)
if(!vis[p->t]) tarjan(p->t),low[v]=min(low[v],low[p->t]);
else if(vst[p->t]) low[v]=min(low[v],dfn[p->t]);
if(low[v]==dfn[v])
{
nc++;
while(st[top+1]!=v) {vst[st[top]]=0;col[st[top--]]=nc;}
}
}
bool check(int v)
{
for(int i=1;i<=2*n;i++)
con[i]=NULL;
for(int i=1;i<=n;i++)
{
int Lx,Rx,Ly,Ry;
Lx=lower_bound(e+1,e+2*n+1,(node){rx[i]-v+1,0})-e;
Rx=upper_bound(e+1,e+2*n+1,(node){rx[i]+v-1,0})-e-1;
Ly=lower_bound(e+1,e+2*n+1,(node){ry[i]-v+1,0})-e;
Ry=upper_bound(e+1,e+2*n+1,(node){ry[i]+v-1,0})-e-1;
if(Lx<=Rx)xtr->ade(i,Lx,g[i]-1),xtr->ade(i,g[i]+1,Rx);
if(Ly<=Ry)xtr->ade(i+n,Ly,g[i+n]-1),xtr->ade(i+n,g[i+n]+1,Ry);
}
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
tim=top=nc=0;
for(int i=1;i<=num;i++)
if(!vis[i]) tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n]) return 0;
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&rx[i],&ry[i]);
e[2*i-1].d=rx[i];e[2*i-1].b=i;
e[2*i].d=ry[i];e[2*i].b=i+n;
}
sort(e+1,e+2*n+1);
num=2*n;
(xtr=new tree)->build(1,2*n);
int L=0,R;
if(n<=1000) R=1e9;
else R=28000;
while(L<R)
{
int mid=(L+R)>>1;
if(check(mid)) L=mid+1;
else R=mid;
}
printf("%d",L-1);
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10010;
const int maxd=40010;
int n,num,tim,top,nc,rx[maxn],ry[maxn],g[maxn<<1],dfn[maxd],low[maxd],col[maxd],st[maxd];
bool vis[maxd],vst[maxd];
struct edge
{
int t;
edge *next;
}*con[maxd];
struct node
{
int d,b;
bool operator <(const node &x) const{return d<x.d;}
}e[maxn<<1];
void ins(int x,int y)
{
if(y==0||x==y) return;
edge *p=new edge;
p->t=y;
p->next=con[x];
con[x]=p;
}
struct tree
{
int l,r,id;
tree *ls,*rs;
tree()
{
ls=rs=NULL;
l=r=id=0;
}
void update()
{
id=++num;
ins(id,ls->id);
ins(id,rs->id);
}
void build(int lx,int rx)
{
l=lx;r=rx;
if(l==r)
{
if(e[l].b>n) id=e[l].b-n;
else id=e[l].b+n;
g[e[l].b]=l;
return ;
}
int mid=(l+r)>>1;
(ls=new tree)->build(lx,mid);
(rs=new tree)->build(mid+1,rx);
update();
}
void ade(int bg,int lx,int rx)
{
if(lx>rx) return;
if(l==lx&&r==rx) {ins(bg,id); return;}
int mid=(l+r)>>1;
if(rx<=mid) ls->ade(bg,lx,rx);
else if(lx>mid) rs->ade(bg,lx,rx);
else ls->ade(bg,lx,mid),rs->ade(bg,mid+1,rx);
}
}*xtr;
void tarjan(int v)
{
vis[v]=vst[v]=1;
low[v]=dfn[v]=++tim;
st[++top]=v;
for(edge *p=con[v];p;p=p->next)
if(!vis[p->t]) tarjan(p->t),low[v]=min(low[v],low[p->t]);
else if(vst[p->t]) low[v]=min(low[v],dfn[p->t]);
if(low[v]==dfn[v])
{
nc++;
while(st[top+1]!=v) {vst[st[top]]=0;col[st[top--]]=nc;}
}
}
bool check(int v)
{
for(int i=1;i<=2*n;i++)
con[i]=NULL;
for(int i=1;i<=n;i++)
{
int Lx,Rx,Ly,Ry;
Lx=lower_bound(e+1,e+2*n+1,(node){rx[i]-v+1,0})-e;
Rx=upper_bound(e+1,e+2*n+1,(node){rx[i]+v-1,0})-e-1;
Ly=lower_bound(e+1,e+2*n+1,(node){ry[i]-v+1,0})-e;
Ry=upper_bound(e+1,e+2*n+1,(node){ry[i]+v-1,0})-e-1;
if(Lx<=Rx)xtr->ade(i,Lx,g[i]-1),xtr->ade(i,g[i]+1,Rx);
if(Ly<=Ry)xtr->ade(i+n,Ly,g[i+n]-1),xtr->ade(i+n,g[i+n]+1,Ry);
}
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
tim=top=nc=0;
for(int i=1;i<=num;i++)
if(!vis[i]) tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n]) return 0;
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&rx[i],&ry[i]);
e[2*i-1].d=rx[i];e[2*i-1].b=i;
e[2*i].d=ry[i];e[2*i].b=i+n;
}
sort(e+1,e+2*n+1);
num=2*n;
(xtr=new tree)->build(1,2*n);
int L=0,R;
if(n<=1000) R=1e9;
else R=28000;
while(L<R)
{
int mid=(L+R)>>1;
if(check(mid)) L=mid+1;
else R=mid;
}
printf("%d",L-1);
return 0;
}