自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:38:22，当前版本为作者最后更新于2022-05-15 19:23:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个 $O(n\log V)$ 的做法。

首先这个走路径明显没用，实际上相当于每一列只能选一个元素。

考虑排序后的序列。我们先将 $2n$ 个元素排序去重，然后枚举点对检查是否可能为答案。

设 $g(i,j)$ 代表 $|f_i-f_j|$，那么我们只需要令所有 $g(x,y)<g(i,j)$ 的 $(x,y)$ 不能够同时选取即可。

可以大力枚举 $(x,y)$，然后建立 2-SAT 模型。正确性显然，复杂度 $O(n^4)$。

发现枚举 $(i,j)$ 没有什么意义，所以直接枚举 $g(i,j)$。

然后发现判定是有单调性什么的东西。。。于是直接二分就可以得到 $O(n^2\log V)$ 的做法了。

发现一件事情，在排序后的 $x$，对于 $y$ 来说 $x$ 一定是连续的一段。

也就是说在 2-sat 的加边中需要做一个区间加边。

这个线段树容易做到 $O(n\log n\log V)$，猫树容易做到 $O(n\log V)$，但是 $O(n\log n)$ 空间。

不过我们还有 $O(n)$ 空间的做法。

需要用到一个 trick（好像叫 baka's trick？）

大概就是说，对于 $y$ 递增，$x$ 一定也递增。所以是一个尺取的过程。

具体地，我们设有三个变量：$L,R,mid$，对于 $i\in[L,mid]$ 有 $S[i]=merge(S[i+1],F[i])$，对于 $i\in(mid,R]$ 有 $S[i]=merge(S[i-1],F[i])$。然后 $S[mid]=F[mid],S[mid-1]=F[mid-1]$。

然后在尺取的时候会出现 $L\geq mid$，这个时候令 $mid=R-1$，重构即可。

这个 $merge$ 在这里对应的就是连边什么的东西。

容易知道这个的空间和时间都是线性的，所以能够做到 $O(n\log V)$ 时间 $O(n)$ 空间。

但是因为各种常数导致空间和时间只比线段树略优

#include<algorithm>
#include<cstdio>
#include<cctype>
#define For(o) for(int o=0;o^2;++o)
const int M=1e5+5,N=M*12;
int n,tot,id[2][M],val[2][M],f[M<<1][2],g[M<<1][2];int len,CB[M<<1],lsh[M<<1];
int tp,dfc,SCC,bl[N],stk[N],dfn[N],low[N];
bool itk[N];int cnt,h[N];
struct Edge{
	int v,nx;
}e[N*4];
inline void Add(const int&u,const int&v){
	e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
}
inline int min(const int&a,const int&b){
	return a>b?b:a;
}
inline void Tarjan(const int&u){
	dfn[u]=low[u]=++dfc;itk[stk[++tp]=u]=true;
	for(int v,E=h[u];E;E=e[E].nx){
		!dfn[v=e[E].v]?Tarjan(v),low[u]=min(low[u],low[v]):itk[v]&&(low[u]=min(low[u],dfn[v]));
	}
	if(low[u]==dfn[u]){
		int v;++SCC;do itk[v=stk[tp--]]=false,bl[v]=SCC;while(u!=v);
	}
}
inline void Clear(){
	for(int i=1;i<=tot;++i)h[i]=bl[i]=dfn[i]=low[i]=0;tot=cnt=dfc=SCC=0;
}
inline int read(){
	int n(0);char s;while(!isdigit(s=getchar()));while(n=n*10+(s&15),isdigit(s=getchar()));return n;
}
inline bool check(const int&k){
	Clear();for(int i=1;i<=len;++i)For(x)f[i][x]=++tot;
	for(int i=1;i<=n;++i){
		Add(f[id[0][i]][1],f[id[1][i]][0]);Add(f[id[1][i]][1],f[id[0][i]][0]);
		Add(f[id[0][i]][0],f[id[1][i]][1]);Add(f[id[1][i]][0],f[id[0][i]][1]);
	}
	For(t)g[1][t]=++tot;
	Add(g[1][0],f[1][0]);Add(g[1][1],f[1][1]);
	Add(f[1][0],g[1][0]);Add(f[1][1],g[1][1]);
	for(int mid(0),L(1),i=2;i<=len;++i){
		while(L<i&&lsh[i]-lsh[L]>=k)++L;if(L==i)continue;
		if(L>mid){
			for(int k=L;k<=i;++k)For(t)g[k][t]=++tot;
			Add(g[i][0],f[i][0]);Add(g[i-1][0],f[i-1][0]);
			Add(f[i][1],g[i][1]);Add(f[i-1][1],g[i-1][1]);
			for(int k=i-2;k>=L;--k){
				Add(g[k][0],g[k+1][0]);Add(g[k][0],f[k][0]);
				Add(g[k+1][1],g[k][1]);Add(f[k][1],g[k][1]);
			}
			mid=i-1;
		}
		else{
			For(t)g[i][t]=++tot;
			Add(g[i][0],g[i-1][0]);Add(g[i][0],f[i][0]);
			Add(g[i-1][1],g[i][1]);Add(f[i][1],g[i][1]);
			Add(f[i][1],g[i-1][0]);Add(g[i-1][1],f[i][0]);
		}
		Add(f[i][1],g[L][0]);Add(g[L][1],f[i][0]);
	}
	For(o)for(int i=1;i<=len;++i)if(!dfn[f[i][o]])Tarjan(f[i][o]);
	for(int i=1;i<=len;++i)if(bl[f[i][0]]==bl[f[i][1]])return false;return true;
}
signed main(){
	n=read();read();read();read();
	For(o)for(int i=1;i<=n;++i)lsh[++len]=val[o][i]=read();std::sort(lsh+1,lsh+len+1);
	For(o)for(int i=1;i<=n;++i)id[o][i]=std::lower_bound(lsh+1,lsh+len+1,val[o][i])-lsh,id[o][i]+=CB[id[o][i]]++;
	int L(0),R(100000000/(n-1)+5),mid,ans(0);while(L<=R)check(mid=L+R>>1)?L=mid+1,ans=mid:R=mid-1;
	printf("%d",ans);
}