AtCoder Regular Contest 069 F Flags 二分，2-sat，线段树优化建图

链接

大意

在数轴上放上n个点，点i可能的位置有\(x_i\)或者\(y_i\)

思路

首先最大值最小，考虑二分答案。

如何check呢。

只有两个坐标，考虑2-sat.

可是边有点多，存不下来，考虑线段树优化建图。

如何建图。

先按照做坐标排序，我们有两个点的范围

[id[x]-mid,id[x]+mid],[id[y]-mid,id[y]+mid]。

这个显然是z选了，区间内就不选，那就选另一个喽。

连区间的补集是不明智的，连点的补集。

细节

这里build直接交换了两个点的位置，%Refun

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+7;

int read()  {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,id[N],mmp,val[N],pos[N];

struct edge {

    int id,val,type;

    bool operator < (const edge &b) const {

        return val<b.val;

    }

}a[N];

struct node {int v,nxt;}e[N<<1];

int head[N],tot;

void add(int u,int v) {

    e[++tot].v=v;

    e[tot].nxt=head[u];

    head[u]=tot;

}

int low[N],dfn[N],stak[N],top,cnt,vis[N],belong[N],scc;

void clear() {

    cnt=scc=tot=0;

    mmp=n+n;

    memset(head,0,sizeof(head));

    memset(dfn,0,sizeof(dfn));

    memset(id,0,sizeof(id));

}

void tarjan(int u) {

    low[u]=dfn[u]=++cnt;

    vis[u]=1;

    stak[++top]=u;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(!dfn[v]) {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        } else if(vis[v]) {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]) {

        ++scc;

        while(stak[top]!=u) {

            vis[stak[top]]=0;

            belong[stak[top]]=scc;

            top--;

        }

        vis[stak[top]]=0;

        belong[stak[top]]=scc;

        top--;

    }

}

namespace seg {

    #define ls rt<<1

    #define rs rt<<1|1

    void build(int l,int r,int rt) {

        if(l==r) return id[rt]=pos[((a[l].id-1)^1)+1],void();

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

        id[rt]=++mmp;

        build(l,mid,ls);

        build(mid+1,r,rs);

        add(id[rt],id[ls]),add(id[rt],id[rs]);

    }

    void update(int u,int L,int R,int l,int r,int rt) {

        if(L>R) return;

        if(L<=l&&r<=R) return add(u,id[rt]);

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

        if(L<=mid) update(u,L,R,l,mid,ls);

        if(R>mid) update(u,L,R,mid+1,r,rs);

    }

}

bool check(int mid) {

    clear();

    seg::build(1,n+n,1);

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

        int l=upper_bound(val+1,val+n+n+1,val[i]-mid)-val;

        int r=lower_bound(val+1,val+n+n+1,val[i]+mid)-val-1;

        seg::update(i,max(l,1),i-1,1,n+n,1);

        seg::update(i,i+1,min(r,2*n),1,n+n,1);

        // printf("%d -> [%d,%d]\n",i,l,i-1);

        // printf("%d -> [%d,%d]\n",i,i+1,r);

     }

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

        if(!dfn[i])

            tarjan(i);

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

        if(belong[pos[i]]==belong[pos[i+1]]) return 0;

    return 1;

}

int main() {

    n=read();

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

        a[2*i-1].id=2*i-1,a[2*i-1].val=read();

        a[2*i].id=2*i,a[2*i].val=read();

    }

    sort(a+1,a+1+n+n);

    for(int i=1;i<=n+n;++i) pos[a[i].id]=i,val[i]=a[i].val;

    int l=0,r=1e9,ans=0;

    while(l<=r) {

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

        if(check(mid)) l=mid+1,ans=mid;

        else r=mid-1;

    }

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

    return 0;

}

巴特西

AtCoder Regular Contest 069 F Flags 二分，2-sat，线段树优化建图

AtCoder Regular Contest 069 F Flags 二分，2-sat，线段树优化建图

链接

大意

思路

细节

代码

最新文章

热门文章