[??记录]AT2336 [ARC069D] Flags

command_block · 2021-05-12 14:39:08 · 个人记录

题意 ： 将 N 个标志放在数轴上。第 i 个标志可以放置在坐标 a_i 或 b_i 上。

求出两个标志之间最小距离的最大值。

• |b_i-a_j|\leq mid$ : $b_i\rightarrow b_j
• |a_i-b_j|\leq mid$ : $a_i\rightarrow a_j
• |b_i-b_j|\leq mid$ : $b_i\rightarrow a_j

缩点后，若 a_i,b_i 在同一个联通块内，则无解。

不难用（两颗）线段树优化建边。复杂度为 O(n\log^2 n)。

常数大得有点离谱……

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 10500
using namespace std;
struct Line{int t,nxt;}l[MaxN*200];
int fir[MaxN*4],tl;
void adl(int u,int v)
{l[++tl]=(Line){v,fir[u]};fir[u]=tl;}
int dfn[MaxN*4],low[MaxN*4],tim,stk[MaxN*4],top,col[MaxN*4],Bcnt;
void tar(int u)
{
  dfn[stk[++top]=u]=low[u]=++tim;
  for (int i=fir[u],v;i;i=l[i].nxt)
    if (!dfn[v=l[i].t])
      {tar(v);low[u]=min(low[u],low[v]);}
    else if (!col[v])low[u]=min(low[u],dfn[v]);
  if (low[u]==dfn[u]){
    Bcnt++;
    while(stk[top+1]!=u)
      col[stk[top--]]=Bcnt;
  }
}
int wfl,wfr,wfc,tn,n;
struct SGT
{
  int p[MaxN<<2],lp[MaxN];
  void build(int l=1,int r=n,int u=1)
  {
    if (l==r){p[u]=lp[l];return ;}
    int mid=(l+r)>>1;p[u]=++tn;
    build(l,mid,u<<1);
    build(mid+1,r,u<<1|1);
    adl(p[u],p[u<<1]);adl(p[u],p[u<<1|1]);
  }
  void add(int l=1,int r=n,int u=1)
  {
    if (wfl<=l&&r<=wfr){adl(wfc,p[u]);return ;}
    int mid=(l+r)>>1;
    if (wfl<=mid)add(l,mid,u<<1);
    if (mid<wfr)add(mid+1,r,u<<1|1);
  }
}Ta,Tb;
int a[MaxN],b[MaxN],xa[MaxN],xb[MaxN],ta[MaxN],tb[MaxN];
bool chk(int lim)
{
  for (int i=1;i<=tn;i++)dfn[i]=fir[i]=col[i]=0;
  tl=0;tn=2*n;
  Ta.build();Tb.build();
  for (int i=1;i<=n;i++){
    wfc=i;
    int l=a[i]-lim+1,r=a[i]+lim-1,mid=ta[i];
    wfl=lower_bound(xa+1,xa+n+1,l)-xa;wfr=mid-1;
    if (wfl<=wfr)Ta.add();
    wfl=mid+1;wfr=upper_bound(xa+1,xa+n+1,r)-xa-1;
    if (wfl<=wfr)Ta.add();
    wfl=lower_bound(xb+1,xb+n+1,l)-xb;
    wfr=upper_bound(xb+1,xb+n+1,r)-xb-1;
    if (wfl<=wfr)Tb.add();
    wfc=i+n;
    l=b[i]-lim+1,r=b[i]+lim-1;
    wfl=lower_bound(xa+1,xa+n+1,l)-xa;
    wfr=upper_bound(xa+1,xa+n+1,r)-xa-1;
    if (wfl<=wfr)Ta.add();
    mid=tb[i];
    wfl=lower_bound(xb+1,xb+n+1,l)-xb;wfr=mid-1;
    if (wfl<=wfr)Tb.add();
    wfl=mid+1;wfr=upper_bound(xb+1,xb+n+1,r)-xb-1;
    if (wfl<=wfr)Tb.add();
  }
  for (int i=1;i<=2*n;i++)
    if (!dfn[i])tar(i);
  for (int i=1;i<=n;i++)
    if (col[i]==col[i+n])return 0;
  return 1;
}
bool cmpA(int A,int B){return a[A]<a[B];}
bool cmpB(int A,int B){return b[A]<b[B];}
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%d%d",&a[i],&b[i]);
    xa[i]=a[i];xb[i]=b[i];
    Ta.lp[i]=Tb.lp[i]=i; 
  }
  sort(Ta.lp+1,Ta.lp+n+1,cmpA);sort(Tb.lp+1,Tb.lp+n+1,cmpB);
  for (int i=1;i<=n;i++){
    ta[Ta.lp[i]]=tb[Tb.lp[i]]=i;
    Ta.lp[i]+=n;
  }sort(xa+1,xa+n+1);sort(xb+1,xb+n+1);
  int l=0,r=1000000000,mid;
  while(l<r){
    mid=(l+r+1)>>1;
    if (chk(mid))l=mid;
    else r=mid-1;
  }printf("%d",r);
  return 0;
}