[ARC069F]Flags 题解

因为一个小错误整整调了一天 qwq

除去 2-SAT 部分没学过去学了一下，其它部分都想出来了，四舍五入我自己写了一道 Cu，好欸（虽然这 Cu 好像非常水QAQ）。

F - Flags

一条数轴上有 \(n\) 个旗帜，第 \(i\) 个旗的位置可能是 \(x_i\) 或 \(y_i\)，最大化旗帜间两两距离的最小值。

\(1\le n\le 10^4,1\le x_i,y_i\le 10^9\)

最大化最小值，直接二分答案，设当前二分到的值为 \(d\)。

为了方便，我们称 \(x_i\) 和 \(y_i\) 互为「反点」。

将所有 \(x_i,y_i\) 在数轴上升序排序，考虑取了一个点 \(x\)，则 \((x-d,x+d)\) 之间的点都取不了，也就是说，我们只能取 \(x\) 或 \((x-d,x+d)\) 中的点这两种之一。换言之，如果取了 \(x\)，就只能取 \((x-d,x+d)\) 中的点的「反点」。

这个是 2-SAT 问题的经典模型，我们将 \(x\) 和这些「反点」连有向边，跑 Tarjan 算 SCC，如果互为「反点」的两个点在同一个 SCC 中，则判定无解，反之有解，构造方法珂以去 2-SAT 的模板题题解里学，因为此题仅需判定，此处略过。

此时还有一个问题：如果暴力连边的话边数会非常非常多，时间和空间可能扛不住。

这题 5s 1GB 时空？直接暴力莽！（

我们要用到一个叫线段树优化建图的 Trick，模板见 [CF786B]Legacy，而且此题只需要由单点向区间连边，那么只需要建出一棵线段树，父节点向子节点连边即可。

总时间复杂度 \(\mathcal O(n\log n\log x_i)\)

Code

// Problem: [ARC069F] Flags
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc069_d
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define fir first
#define sec second
#define pb emplace_back
using pii = std::pair<int,int>;

const int maxn = 2e4 + 5;
int n,a[maxn][2];
std::vector<pii> s;
std::vector<int> G[maxn << 2];
int ls[maxn << 2],rs[maxn << 2],id[maxn << 2],num;

void build(int i,int l,int r) {
	ls[i] = l;
	rs[i] = r;
	num = std::max(num , i);
	if(l == r) {
		id[s[l - 1].fir + (!s[l - 1].sec) * n] = i;
		return ;
	}
	int mid = l + r >> 1;
	build(i << 1 , l , mid);
	build(i << 1 | 1 , mid + 1 , r);
	G[i].pb(i << 1);
	G[i].pb(i << 1 | 1);
	return ;
}

void connect(int i,int l,int r,int pos) {
	if(ls[i] >= l&&rs[i] <= r) {
		G[pos].pb(i);
		return ;
	}
	if(ls[i] > r||rs[i] < l)return ;
	int mid = ls[i] + rs[i] >> 1;
	if(l <= mid)connect(i << 1 , l , r , pos);
	if(r > mid)connect(i << 1 | 1 , l , r , pos);
	return ;
}

int cnt,low[maxn << 2],dfn[maxn << 2],stk[maxn << 2],tp,col[maxn << 2],tot;
bool ins[maxn << 2];

void init() {
	for(int i = 1;i <= num;++ i)
		G[i].clear();
	tp = cnt = tot = num = 0;
	memset(low , 0 , sizeof(low));
	memset(dfn , 0 , sizeof(dfn));
	memset(col , 0 , sizeof(col));
	memset(ins , false , sizeof(ins));
	memset(ls , 0 , sizeof(ls));
	memset(rs , 0 , sizeof(rs));
	memset(id , 0 , sizeof(id));
	return ;
}

void tarjan(int u) {
	low[u] = dfn[u] = ++ cnt;
	stk[++ tp] = u;
	ins[u] = true;
	for(auto& v : G[u]) {
		if(!dfn[v])
			tarjan(v),low[u] = std::min(low[u] , low[v]);
		else if(ins[v])
			low[u] = std::min(low[u] , dfn[v]);
	}
	if(dfn[u] == low[u]) {
		++ tot;
		do {
			ins[stk[tp]] = false;
			col[stk[tp]] = tot;
		} while(tp&&stk[tp --] != u);
	}
	return ;
}

bool check(int d) {
	init();
	build(1 , 1 , (int)s.size());
	for(int i = 1,l = 1,r = 1;i <= (int)s.size();++ i) {
		while(l < i&&a[s[i - 1].fir][s[i - 1].sec] - a[s[l - 1].fir][s[l - 1].sec] >= d)
			++ l;
		while(r < (int)s.size()&&a[s[r].fir][s[r].sec] - a[s[i - 1].fir][s[i - 1].sec] < d)
			++ r;
		if(l < i)connect(1 , l , i - 1 , id[s[i - 1].fir + s[i - 1].sec * n]);
		if(i < r)connect(1 , i + 1 , r , id[s[i - 1].fir + s[i - 1].sec * n]);
	}
	for(int i = 1;i <= num;++ i)
		if(!dfn[i])tarjan(i);
	for(int i = 1;i <= n;++ i) {
		if(col[id[i]] == col[id[i + n]])
			return false;
	}
	return true;
}

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)
		scanf("%d %d",&a[i][0],&a[i][1]),s.pb(i , 0),s.pb(i , 1);
	std::sort(s.begin() , s.end() , [&](const pii& p,const pii& q) {
		return a[p.fir][p.sec] < a[q.fir][q.sec];
	});
	
	int l = 0,r = 1e9;
	while(l <= r) {
		int mid = l + r >> 1;
		if(check(mid))l = mid + 1;
		else r = mid - 1;
	}
	
	printf("%d\n",r);
	return 0;
}