【ARC069F】Flags 2-sat+线段树优化建图+二分

2024-04-11 14:15:49

Description

数轴上有 n 个旗子，第 ii 个可以插在坐标 xi或者 yi，最大化两两旗子之间的最小距离。

Input

第一行一个整数 N。

接下来 N 行每行两个整数 xi,yi

Output

一个整数表示答案。

Sample Input

Sample Output

Sample #1

4

Sample #2

0

Sample #3

17

HINT

2≤N≤10^4

1≤xi,yi≤10^9

Sol

线段树优化建图+2-sat+二分。

首先我们二分答案k，然后把一个点向离他距离为k以内的点的反点连边（2-sat的边表示依赖关系），之后直接判断有没有解，但是显然这样会TLE，因为边的个数是\(n^2\)级别的。

所以考虑线段树优化建图，步骤为：

1.按照2n个点排序，建出线段树，每个点向他的父亲连边，最底层点向这个点代表的点的反点连边（因为2-sat连的是反点，别的题没有必要）

2.对于每个点进行编号（一共2n个）。

3.我们考虑每个点，找到和他距离k以内的点的两段区间，然后用这个点按照线段树区间查找的方式向logn个区间连边。（注意一定要跳过自己对应的点，因为这代表着自己的反点，不能连边）

中间有点细节，要注意一下。

之后就是2-sat的经典应用了。

Code

#include <bits/stdc++.h>

using namespace std;

struct seg{int l,r,id;seg(int l=0,int r=0,int id=0):l(l),r(r),id(id){}}s[500005];

int n,P,Index,L,p[100005][2],dfn[100005],low[100005],in[100005],cnt,bel[100005],b[100005],x[100005],y[100005],X[100005],Y[100005],vis[100005];

pair<int,int>pos[100005];vector<int>e[100005];stack<int>q;

void build(int x,int L,int R)

{

	s[x]=seg(L,R,++P);

	if(x>>1) e[s[x>>1].id].push_back(s[x].id);

	if(L==R){e[s[x].id].push_back(p[pos[L].first][pos[L].second^1]);return;}

	int mid=(L+R)>>1;build(x*2,L,mid);build(x*2+1,mid+1,R);

}

void ins(int x,int L,int R,int u)

{

	if(L>R) return;

	if(s[x].l==L&&s[x].r==R){e[u].push_back(s[x].id);return;}

	int mid=(s[x].l+s[x].r)>>1;

	if(R<=mid) ins(x*2,L,R,u);else if(L>mid) ins(x*2+1,L,R,u);

	else ins(x*2,L,mid,u),ins(x*2+1,mid+1,R,u);

}

void tarjan(int x)

{

	dfn[x]=low[x]=++Index;in[x]=1;q.push(x);

	for(int i=0;i<e[x].size();i++)

		if(!dfn[e[x][i]]) tarjan(e[x][i]),low[x]=min(low[x],low[e[x][i]]);

		else if(in[e[x][i]]) low[x]=min(low[x],dfn[e[x][i]]);

	if(dfn[x]==low[x]) for(cnt++;;){int now=q.top();q.pop();in[now]=0;bel[now]=cnt;if(now==x) break;}

}

bool chk(int k)

{

	P=cnt=Index=0;for(int i=0;i<=n*5;i++) e[i].clear();while(!q.empty()) q.pop();

	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(in,0,sizeof(in));memset(bel,0,sizeof(bel));

	for(int i=1;i<=n;i++) p[i][0]=++P,p[i][1]=++P;

	build(1,1,L);

	for(int i=1;i<=n;i++)

	ins(1,upper_bound(b+1,b+L+1,X[i]-k)-b,x[i]-1,p[i][0]),ins(1,x[i]+1,lower_bound(b+1,b+L+1,X[i]+k)-b-1,p[i][0]),

	ins(1,upper_bound(b+1,b+L+1,Y[i]-k)-b,y[i]-1,p[i][1]),ins(1,y[i]+1,lower_bound(b+1,b+L+1,Y[i]+k)-b-1,p[i][1]);

	for(int i=1;i<=P;i++) if(!dfn[i]) tarjan(i);int ok=1;

	for(int i=1;i<=n;i++) if(bel[p[i][0]]==bel[p[i][1]]) ok=0;

	return ok;

}

int find(int I,int P,int x)

{

	int res,l=1,r=L;

	for(int mid=(l+r)>>1;l<=r;mid=(l+r)>>1)

	{

		if(b[mid]==x&&!vis[mid]) res=mid,r=mid-1;

		else if(b[mid]>x) r=mid-1;else l=mid+1;

	}

	vis[res]=1;pos[res]=make_pair(I,P);return res;

}

int main()

{

	scanf("%d",&n);int l=0,r=1e9,ans;

	for(int i=1;i<=n;i++) scanf("%d%d",&X[i],&Y[i]),b[++L]=X[i],b[++L]=Y[i];

	sort(b+1,b+L+1);

	for(int i=1;i<=n;i++) x[i]=find(i,0,X[i]),y[i]=find(i,1,Y[i]);

	for(int mid=(l+r)>>1;l<=r;mid=(l+r)>>1) if(chk(mid)) l=mid+1,ans=mid;else r=mid-1;

	printf("%d\n",ans);

}

码农公寓