2-SAT+优化建图 P8358题解

· · 题解

一个 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);
}